프로그래머스 - 단속카메라(Java)

그리디 문제입니다.

 

중간중간에 들어오는 곳과 나가는 곳이 존재하는 고속도로에 차량이 고속도로에 존재하는 좌표가 주어졌을 때, 모든 차량을 확인하는 카메라를 최소로 설치하는 개수를 구하는 문제입니다.

카메라의 개수를 구하는 것이지, 카메라의 정확한 위치를 구하는 문제가 아니기 때문에 그리디를 생각해 볼 수 있습니다.

 

고속도로에 처음으로 들어오는 차량을 확인하기 위해서는 최소한 해당 차량이 나가는 지점에는 설치해야 합니다.

위 그림에서는 최소 {-15} 위치에 카메라를 설치해야 합니다.

여기서 알 수 있다 싶이, 각 차량의 나가는 지점을 기준으로 오름차순 정렬을 하여 카메라를 설치하면 됩니다.

다음 카메라 설치 위치는 이전 카메라의 위치에 포함되지 않는 곳을 설치하면 됩니다.

 

[구현 코드]

import java.util.*;

class Solution {
    public static int solution(int[][] routes) {
        int answer = 0;

        Arrays.sort(routes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                // 끝 지점 기준으로 정렬
                return o1[1] - o2[1];
            }
        });

        int camera = (-1) * (30_001);
        for (int[] route : routes) {
            int s = route[0];
            int e = route[1];

            // 이전 카메라가 설치한 곳에서 볼 수 없을 때
            if(s > camera){
                // 카메라를 끝 지점에 설치
                camera = e;
                answer++;
            }
        }

        return answer;
    }
}