문제

풀이

이 문제는 앞 차량의 진출 지점이 뒷 차량의 진입 시점보다 뒤에 있으면 한 대의 카메라만 사용해도 된다.
이 원리를 이용해서 routes를 진출 지점을 기준으로 정렬한다.
첫 번 째 route의 진출 지점에 먼저 카메라 하나를 둔다.
그 다음 route에 순차적으로 접근하면서 카메라 위치보다 진입 시점이 뒤인 경우에는 해당 route 진출 지점에 새로운 카메라 하나를 둔다.

코드

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        int answer = 0;
        
        // 진출 지점을 기준으로 정렬
        Arrays.sort(routes, Comparator.comparingInt(route -> route[1]));
        
        int cameraLoc = routes[0][1];
        answer ++;
        
        for (int[] route : routes) {
            if (cameraLoc < route[0]) {
                cameraLoc = route[1];
                answer ++;
            }
        }
        return answer;
    }
}

결과

느낀 점

정렬 때문인지 효율성 3번이 아슬아슬 했지만 나름 잘 푼 것 같다.
사실 정석은 그리디를 이용하는 것 같지만 이게 훨씬 쉽기 때문에 이렇게 풀었다.
다음에는 그리디로 풀어봐야겠다.