Today's Algorithm(2019-01-15)

programmers. 단속카메라

또 탐욕법이라 생각하니 자연스럽게 큰 것을 먼저 처리해야 한다는 생각이 들었고 이번 문제의 경우 길이가 가장 크거나 작은 순으로 하여 각각의 경우 체크하도록 문제를 풀었습니다. 구체적으로 먼저 길이로 정렬을 하였고, 해당 길이 내에서 for문을 돌면서 어느 지점에 단속카메라를 설치하였을 때 가장 겹치는 지점을 찾았고, 그 겹치는 지점에 속하는 구간을 빼내면서 결국 카메라가 몇 개가 필요한 것인지 찾아나갔습니다. 이렇게 하였을 때 정확성에는 문제가 없었지만 역시나 복잡도 때문에 시간초과가 발생하였습니다.

 

결국 다른 방법을 찾아야했습니다. 결국 길이가 중요한 것이 아니었습니다. 진입점과 진출점만 알면 위와 같은 복잡도 없이 쉽게 풀 수 있거든요. 우선 객체를 하나 만들었는데요. 다음과 같습니다.

class Route implements Comparable<Route>{
    int start;
    int end;
    boolean checked;

    public Route(int start, int end, boolean checked) {
        this.start = start;
        this.end = end;
        this.checked = checked;
    }

    @Override
    public int compareTo(Route o) {
        return o.start - this.start;
    }
}

아이디어는 다음과 같습니다.

• 우선 정렬을 해야하는데 진입점이 가장 큰 순으로 정렬을 하여 가장 큰 지점부터 찾아가도록 하겠습니다.
• 그리고 다시 안에서 Route객체들을 돌리는데 이때는 해당 진입점이 진출점 안에 존재하는지 유무를 조사하고 만약 안에 있다면 checked 값을 true 로 바꿉니다. 이후 checked 된 Route 객체는 진입점을 안 살필 것입니다.
• 해당 과정이 끝나면 answer 을 증감시킵니다.

class Solution {
    public int solution(int[][] routes) {
        int answer = 0;
        List<Route> routeList = initRoute(routes);
        Collections.sort(routeList);

        for (Route route : routeList) {
            if(route.checked) continue;
            int start = route.start;

            for (Route route1 : routeList) {
                if(route1.checked == false && start <= route1.end) route1.checked = true;
            }
            answer++;
        }

        return answer;
    }

    private List<Route> initRoute(int[][] routes) {
        List<Route> routeList = new ArrayList<>();
        for (int[] route : routes) {
            if(route[0] > route[1]) {
                int temp = route[0];
                route[0] = route[1];
                route[1] = temp;
            }
            routeList.add(new Route(route[0], route[1], false));
        }
        return routeList;
    }
}

class Route implements Comparable<Route>{
    int start;
    int end;
    boolean checked;

    public Route(int start, int end, boolean checked) {
        this.start = start;
        this.end = end;
        this.checked = checked;
    }

    @Override
    public int compareTo(Route o) {
        return o.start - this.start;
    }
}

 

 

programmers. 저울

처음엔 binary를 이용하여 모든 경우를 구한다음 다시 반복문을 돌면서 없는 수를 찾았습니다(물론 시간 초과가 날 것이라 예상은 했지만..). 역시나 시간초과가 발생하였습니다. 다른 방법이 떠오르지 않아 다른 사람들의 코드를 참고하였는데요. 전형적인 방법이 있더라구요. 그 안의 수학적 원리가 있겠지만 저는 자세히 깨닫진 못했습니다.. 그렇기 때문에 코드부터 보겠습니다.

class Solution {
    public int solution(int[] weight) {
        int answer = 1;
        Arrays.sort(weight);
	
        for (int i : weight) {
            if(answer < i) break;
            answer += i;
        }
        
        return answer;
    }
}

우선 answer 값은 1로 시작합니다. 여기서 +1로부터 시작했다는 점을 기억해야 합니다. +1은 허상입니다. 그렇기 때문에 계속 더해주다가 answer < i 일 때 answer을 반환할 수 있는 것입니다. 신기하기도 answer += i 보다 작은 수가 경우의 수로 모두 존재합니다. 그 이유는 몇 개를 써보면 알겠지만 i보다 작은 수가 이미 존재하기 때문에 (그 작은 수들 + i)가 다 커버되는 것입니다. 저도 더이상 어떻게 설명해야 할지 모르겠지만 써보면서 확인해보시기 바랍니다.