[프로그래머스] Lv3 단속 카메라

접근 방식

최소한의 카메라로 모든 차량을 단속하려면, 가장 많은 차량이 겹치는 종료 지점에 카메라를 설치해야 합니다.

이를 위해, 먼저 차량의 이동 범위를 "끝 지점" 기준으로 정렬합니다. 정렬된 이동 범위를 기준으로, 가장 먼저 종료되는 지점부터 카메라를 배치하면 최소 개수의 카메라로 모든 차량을 단속할 수 있습니다.

 

왜 자동차의 끝지점을 기준으로 정렬해 주어야 할까요?

 

자동차의 이동 범위를 끝 지점을 기준으로 오름차순 정렬하면, 가장 먼저 종료되는 차량부터 고려할 수 있습니다.
즉, 가장 먼저 끝나는 자동차를 단속하는 위치에 카메라를 설치하면, 이후의 자동차들도 최대한 많이 커버할 수 있습니다.

 

왜 하필 끝 지점인가요? 시작지점은 안되나요?

 

상황을 예시로 들겠습니다. A자동차가 이동하는 범위는 [1,4] B자동차가 이동하는 범위는 [2,5] C자동차가 이동하는 범위는 [4,6]입니다.

만약 겹치는 범위의 시작지점을 기준으로 카메라를 설치하게 되면 2번 위치와 4번 위치에 카메라가 설치되게 됩니다. 2개의 카메라가 필요하게 됩니다. 하지만, 끝지점을 기준으로 카메라를 설치하게되면 4번 위치에 1개만 설치하면 됩니다.

 

 

하나의 예시를 보면서 제가 생각한 방법이 맞는지 증명하겠습니다.

 

문제에서 주어진 예시입니다. 자동차가 지나가는 범위를 그림으로 표현하면 아래와 같습니다.

 

그림에서 제일 많이 겹치는 부분의 위치는 -18,-15, -14, -13, -5입니다.

두 위치는 각각 2개의 자동차가 카메라가 지나갈 수 있게 해줍니다.

 

끝 지점을 기준으로 정렬하면 다음과 같습니다.

 

-18, -15, -14, -13, -5 중 어느 지점에 카메라를 세워야 할까요?

 

각 차량이 이동하는 범위와 제일 많이 겹치는 끝지점 위치에 카메라를 세워야 합니다.

-18, -14는 끝지점이 아니므로 제외합니다. 남은 지점은 -15, -13, -5 지점이 남았습니다.

첫번째로 -15지점에 카메라를 설치합니다. -13지점과 -5지점이 남았는데, -13지점은 -15지점에 카메라를 세웠기 때문에, [-14,-5]범위의 자동차만 단속할 수 있게 됩니다. 그에 비해 -5지점의 카메라는 [-13,-5]과 [-5,-3] 두 지점의 자동차를 단속하므로, 최소의 카메라 갯수를 위해선 -5지점을 선택합니다. 

 

정리하면, 최소한의 카메라로 모든 차량을 단속하려면, 가장 많은 차량이 겹치는 종료 지점에 카메라를 설치해야 합니다.

이를 위해, 먼저 차량의 이동 범위를 "끝 지점" 기준으로 정렬합니다. 정렬된 이동 범위를 기준으로, 가장 먼저 종료되는 지점부터 카메라를 배치하면 최소 개수의 카메라로 모든 차량을 단속할 수 있습니다.

 

 

풀이 코드

import java.util.*;

class Solution {
    
    public int solution(int[][] routes) {
        
        List<CarRoute> carRoutes = new ArrayList<>();
        
        for(int[] route: routes) {
            carRoutes.add(new CarRoute(route[0], route[1]));
        }
        
        Collections.sort(carRoutes,(o1, o2) -> {
            if(o1.end == o2.end) {
                return o1.start - o2.start;
            }
            
            return o1.end - o2.end;
        });
        
        int cameraCnt = 0;
        int curCameraPosition = -30001;
        
        for(CarRoute carRoute : carRoutes) {
            if(carRoute.start > curCameraPosition) {
                cameraCnt++;
                curCameraPosition = carRoute.end;
            }
        }
        
        return cameraCnt;
    }
    
    public class CarRoute {
        int start;
        int end;
        
        public CarRoute(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
}

 

시간 복잡도

배열 정렬 + 선형 탐색으로 인해 O(NlogN + N)이 걸립니다.

 

출력 결과