BLOG :||

import java.util.*;
class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];

        int x;
        int y;
        for(int i = 1; i<=yellow;++i) {
            if(yellow % i == 0) {
                x = i;
                y = yellow / i;
                if(x == y) {
                    return new int[]{x+2,x+2};
                }
                if((x+y)*2+4 == brown) {
                    if(x < y) {
                        int tmp = y;
                        y = x;
                        x = tmp;
                    }
                    return new int[]{x+2,y+2};
                }
            }
        }
        return answer;
    }
}

yellow와 brown의 개수에 대한 공식을 알면 문제를 어렵지 않게 풀 수 있다.

import java.util.*;

class Solution {
    public int[] solution(int[] answers) {
        int[] answer = {};
        int[] first = {1,2,3,4,5};
        int[] second = {1,3,4,5};
        int[] third = {3,1,2,4,5};
        int[] uAnswer = new int[3];
        //1,2,3,4,5,1,2,3,4,5,1,2,3,4,5
        //1는 (answer % 5 == 0) ? 5 : answer % 5;
        //(answer % 2 == 1) ? 2 : (answer / 2) % 4;
        //1,3,4,5,1,3,4,5
        //2,1,2,3,2,4,2,5,2,1,2,3,2,4,2,5
        //33,11,22,44,55
        //
        for(int i = 0; i<answers.length;++i) {
            
            int f = first[i%5];
            int s = (i%2 == 0) ? 2 : second[(i/2)%4];
            int t = third[(i/2)%5];
            if(f == answers[i])
                uAnswer[0]++;
            if(s == answers[i])
                uAnswer[1]++;
            if(t == answers[i])
                uAnswer[2]++;
        }
        int max = -1;
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i<uAnswer.length;++i) {
            if(uAnswer[i] > max)
                max = uAnswer[i];
        }
        for(int i = 0; i<uAnswer.length;++i) {
            if(uAnswer[i] == max)
                list.add(i+1);
        }
        answer = new int[list.size()];
        for(int i = 0; i<list.size();++i)
            answer[i] = list.get(i);
        return answer;
    }
}

찍는 방법의 규칙성만 찾아내면 되는 문제

import java.util.*;

class Bridge implements Comparable<Bridge>{
    int cost;
    int from;
    int to;
    public Bridge(int cost, int from, int to) {
        this.cost = cost;
        if(from < to) {
            this.from = from;
            this.to = to;
        }
        else {
            this.from = to;
            this.to = from;  
        }
    }
    @Override
    public int compareTo(Bridge b) {
        if(b.cost < cost)
            return 1;
        else if(cost < b.cost)
            return -1;
        else
            return 0;
    }
}
class Solution {
    int[] parent;
    public int solution(int n, int[][] costs) {
        int answer = 0;
        parent = new int[n];
        
        for(int i = 0; i < n;++i)
            parent[i] = i;
        
        List<Bridge> list = new ArrayList<>();
        
        for(int[] cost : costs)
            list.add(new Bridge(cost[2], cost[0], cost[1]));
        
        Collections.sort(list);
        
        for(Bridge bridge : list) {
            if(!isSameParent(bridge.from, bridge.to)) {
                answer += bridge.cost;
                setParent(bridge.from, bridge.to);
            }
        }
        return answer;
    }
    public boolean isSameParent(int i, int j) {
        if(getParent(i) != getParent(j))
            return false;
        return true;
    }
    public int getParent(int i) {
        if(parent[i] != i) {
            return getParent(parent[i]);
        }
        return parent[i];
    }
    public void setParent(int i, int j) {
        if(getParent(i) != i) {
            parent[getParent(j)] = getParent(i);
        } 
        else if(getParent(j) != j) {
            parent[getParent(i)]  = getParent(j);
        }
        else {
            parent[j] = parent[i];
        }
    }
}

크루스칼 알고리즘을 써야 하는 문제이다.

처음 봤을 때는 억... 했지만 크루스칼 알고리즘을 다시 복기하고 나니까 크게 어려운 문제는 아니었다.

크루스칼 알고리즘을 써야하는 문제는 이렇게 생겼구나 하고 기억만 해두면 문제는 없을 것 같다.

까먹지 말아야 할 건 setParent에서 parent[j] = ~~~~가 아니라 parent[getParent(j)] = ~~~~~가 되야 한다는 점.

서로 다른 그룹을 연결하기 위해서는 최상위 부모가 되는 노드끼리 연결을 해주어야 하기 때문.

스터디 공부 하고 관련 문제를 풀어봤는데 재미는 있는데... 이거에 시간 쓸 때가 아닌데 어휴

class Solution {
    public int solution(String name) {
        int answer = 0;
        int nameLen = name.length();
        boolean[] changed = new boolean[nameLen];
        int tmp = 0;
        int trueCount = 0;
        for(int i = 0; i<nameLen;++i) {
            if(name.charAt(i) != 'A') {
                tmp = name.charAt(i)-'A';
                if(tmp < 13)
                    answer += tmp;
                else 
                    answer += (26-tmp);
                changed[i] = true;
                trueCount++;

            }
        }
        changed[0] = false;
        trueCount--;
        
        int min = nameLen;
        int minIndex = -1;
        //0,1,2,3
        //4-3-cursor = 1
        //4-2-cursor = 2
        //4-1-cursor = 3
        // 
        int cursor = 0;
        int distance = 0;
        while(trueCount > 0) {
            min = nameLen;
            minIndex = -1;
            
            for(int i = 0; i<nameLen;++i) {
                if(changed[i] == true) {
                    distance = (cursor > i) ? cursor-i:i-cursor;
                    if(cursor < i) {
                        distance = (nameLen-distance < distance) ? nameLen-distance : distance;
                    }
                    if(min > distance) {
                        min = distance;
                        minIndex = i;
                    }
                }
            }
            changed[minIndex] = false;
            answer += min;
            trueCount--;
            cursor = minIndex;
            
        }
        
        return answer;
    }
}

아 이게 어떻게 레벨2짜리 문제인건지..;;

예전에 문제를 풀었을 때는 글자를 바꾸고 한 칸 옮기고 글자를 바꾸고 한 칸 옮기는 식으로 했었는데 책을 본 효과인지는 모르겠지만.. 글자가 다른 경우를 미리 다 처리하고 나서 옮기는 것에 대해서만 고려할 수 있도록 코드를 짜보니 확실히 깔끔해졌다.

다만 테스트케이스 11에서 틀렸다고 나오는데 다른 사람들 질문 내용을 봐도 감이 안온다. 그리디 알고리즘이라고 할 때 가장 가까운 값으로 이동을 하는 것 외에 고려할게 없을텐데.. 문제가 약간 이상하다고 생각해서 여기까지 하고 넘긴다.

지금은 마땅히 생각나는 문제점을 못찾고 있으니 다음에 한 번 더 봐야겠다.

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        int[] clothes = new int[n];
        for(int l : lost) {
            clothes[l-1]--;
        }
        for(int r : reserve) {
            clothes[r-1]++;
        }
        
        for(int i = 0; i<clothes.length;++i) {
            if(clothes[i] >0 && i > 0 && clothes[i-1] == -1) {
                clothes[i-1]++;
                clothes[i]--;
                System.out.println(i+ " "+ (i-1));
            }
            else if(clothes[i] > 0 && i+1 <clothes.length && clothes[i+1] == -1) {
                clothes[i+1]++;
                clothes[i]--;
                System.out.println(i+ " "+ (i+1));
            }
            /*
            if(clothes[i] > 0 && i+1 <clothes.length) {
                clothes[i+1]++;
                clothes[i]--;
            }*/
            
        }
        for(int i : clothes) {
            System.out.print(i);
            if(i >= 0)
                answer++;
        }
        return answer;
    }
}

처음 풀 때 어디서 꼬였었는데 넘겼다가 오늘 다시 풀어봤다.

clothes[]를 초기화하면 기본적으로 다 0이 들어가 있으므로 0을 옷을 1장 보유한 상태로 가정한다.

도둑맞은걸 빼고 여분을 더해준 뒤해 알고리즘이 시작된다.

왼쪽에서 오른쪽으로 진행될 예정이기 때문에 왼쪽을 우선적으로 빌려주고 왼쪽이 옷을 가지고 있을 경우, 오른쪽에 빌려주는 형태로 진행이 된다.

여분을 계속 우측으로 넘기면 좋지 않을까 싶었지만 옷은 없는 사람한테만 직접 빌려줘야 하나보다.

import java.util.*;
class Solution {
    public String solution(String number, int k) {
        String text = "0";
        int len = number.length();
        k = number.length()-k;
        Stack<String> s = new Stack<>();//stack을 어떻게 유추하나
        s.push(number.substring(0,1));
        for(int i = 1; i<len;++i) {
            while(s.size() > 0 &&Integer.parseInt(s.peek()) < Integer.parseInt(number.substring(i,i+1)) && s.size()-1+len-i >= k) {
                s.pop();
            }
            if(s.size() < k)//pop조건에서 제외되어도 사이즈에 따라 예외처리는 해야 한다.
                s.push(number.substring(i,i+1));
        }
        String t = "";
        while(s.size() > 0) {
            t= s.pop()+t;
        }
        while(true) {
            if(t.charAt(0) == '0')
                t = t.substring(1, t.length());
            else
                break;
        }
        return t;
    }
/*
    public String solution(String number, int k) {
        String text = "0";
        int val = -1;
        int max = getRemoveNumT(0,k,number, val);
        
        return Integer.toString(max);
    }
    public int getRemoveNumT(int originI, int k, String number, int max) {
        String tmp = "";
        for(int i = originI; i<number.length()-k+1;++i) {
            if(i == 0)
                tmp = number.substring(i+1, number.length());
            else {
                tmp = number.substring(0, i)+number.substring(i+1, number.length());
            }
            if(k == 1) {
            	if(max < Integer.parseInt(tmp))
            		max = Integer.parseInt(tmp);
            }
            else {
            	int t = getRemoveNumT(i, k-1, tmp, max);
            	if(t > max)
            		max = t;
            }
        }
		return max;
    }
*/
}

처음에 재귀로 했다가 효율성 테스트에서 시간 초과가 떴었다.

뭐가 문제일까 하면서 다른 사람이 질문한 내용을 봤는데 stack을 쓰면 좋다고 하는 글을 보고...

고민해보고 풀어보니까 감탄이 나오더라.

제외해야 되는 글자 수에 걸리지 않는 한에서

peek()보다 현재 값이 크면 값을 pop()하고 push()를 한다.

코딩테스트에서 문제만 푸는건 요새는 다들 하니까 이런 효율성을 찾으려고 해야 한다..

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        if(people.length == 1)
            return 1;
        Arrays.sort(people);
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i<people.length;++i)
            list.add(people[i]);
        int len = 0;
        int big = 0;
        while(list.size() > 0) {
            len = list.size();
            big = list.get(len-1);
            if(list.size() >1 && big+list.get(0) <= limit) {
                list.remove(list.size()-1);
                list.remove(0);
            }
            else {
                list.remove(list.size()-1);
            }
            answer++;
        }
        
        return answer;
    }
}

인원을 무게 순으로 정렬한다.

가장 무게가 나가는 사람이 가장 가벼운 사람을 태우지 못하면 배 하나 들고 나간다.

태울 수 있으면 태운다. 끝이다.

지금 생각해보니 저걸 list로 하지말고 deque를 쓰는게 좋았을텐데..

deque나 set이나 회사에서 잘 안쓰는 자료구조는 까먹을 때가 많아서 문제다.

import java.util.*;
class route implements Comparable<route>{
    int a;
    int b;
    int c;
    public route(int a, int b, int c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }
    @Override
    public int compareTo(route r) {
        if(a < r.a)
            return -1;
        else if(a > r.a)
            return 1;
        else {
            if(c < r.c)
                return -1;
            else if(c > r.c)
                return 1;
            else 
                return 0;
        }
    }
}

class Solution {
    public int solution(int[][] routes) {
        int answer = 0;
        List<route> list = new ArrayList<>();
        for(int i = 0; i<routes.length;++i) {
            list.add(new route(routes[i][0],i, 0));
            list.add(new route(routes[i][1],i, 1));
        }
        
        Collections.sort(list);
        //Queue<route> stack = new LinkedList<>();
        //int min = list.get(0).a;
        //int max = list.get(list.size()-1).a;
        //stack.add(list.get(0));
        int minC = -30001;
        for(int i = 0; i<list.size();++i) {
            route t = list.get(i);
            if(t.c == 1) {
                if(minC < routes[t.b][0]) {
                    answer++;
                    minC = t.a;
                }
            }
        }
        // c             d
        //-20 1 0, -18 3 0, -14 2 0, -13 3 1, -5 4 0, -5 2 1, -3 4 1, 15 1 1
        
        //들어온 뒤에 처음 나가는 것이 있을 경우 카메라를 놓는다.
        //나간 것이 존재하고 이후에 값이 들어올 경우, 
        return answer;
    }
}

취업한 이후로 블로그 쓰고 싶지 않았는데.. 계속 했어야 했다.

스터디 책에서 그리디 알고리즘이 나왔으므로 관련 문제를 올려본다.

키 포인트는 카메라를 두는 조건을 명확히 설정을 하고 이에 맞춰 코딩을 해야 한다.

일단 차량이 들어오고 나가는 각 시점을 시간 순으로 정렬을 해야겠다 싶어서 이를 따로 쪼개 list에 넣고 정렬을 했다.

차량 진출시점의 최소값이 -30000이었기 때문에 우선 카메라 위치의 min 값으로 -30001을 잡았고

for문을 돌리면서 list 내의 객체가 out일 때(c==1) 마지막 카메라의 위치가 차가 진입한 시점보다 이전이면 나갈때 카메라를 하나 세워주는 식으로 진행했다. 차량의 inout을 시간순으로 정렬했기 때문에 마지막 카메라 위치만 알면 되니까 값을 따로 기억하지는 않고 마지막 카메라 위치만 체크해서 풀면 꽤 간단했다.