단속카메라

문제 정보

• 프로그래머스 Lv.3
• 그리디
• 문제 링크

풀이

최대한 많은 차량이 겹치는 지점에 카메라를 설치할 수 있도록, 각 차량을 반드시 단속할 수 있는 한계선(진출 시점)에 카메라를 설치하는 그리디 전략을 사용한다.

이를 위해서 진출 시점을 기준으로 오름차순 정렬한다.

진입 시점을 기준으로 정렬하면 긴 구간 안에 짧은 구간이 포함된 경우, 짧은 구간의 진출 시점을 놓쳐 카메라를 불필요하게 추가 설치하게 된다.

• e.g routes = [[-20, 10], [-10, -5], [-3, 5]]
  • 이 경우 답은 2지만, 진입 시점을 기준으로 정렬할 경우 3이 반환된다.

또한 진출 시점을 기준으로 정렬해야 ‘(해당 차량을 단속하기 위해서는) 최소한 이 지점에는 카메라를 설치해야 한다’는 한계선이 명확해진다. 동시에, 최대한 뒤에 설치해야 다른 차량과 겹칠 확률이 높아지기 때문에 진출 시점에 설치하는 것이 유리하다.

코드

import java.util.*;
 
class Solution {
    public int solution(int[][] routes) {        
        Arrays.sort(routes, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return a[1] - b[1];
            }
        });
        
        int camera = routes[0][1];
        int answer = 1;
        
        for(int[] route : routes) {
            if (route[0] > camera) {
                answer++;
                camera = route[1];
            }
        }
        
        return answer;
    }
}