[프로그래머스] 탐욕법(Geedy). 단속카메라

https://programmers.co.kr/learn/courses/30/lessons/42884

문제 설명
고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

제한사항
차량의 대수는 1대 이상 10,000대 이하입니다.routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

입출력 예

routes	return
[[-20,-15], [-14,-5], [-18,-13], [-5,-3]]	2

입출력 예
설명-5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.

그리디 문제입니다. 그리디는 기본적으로 정렬 후 최대로 담을 수 있는 경우를 생각하면 되는데요. 이번 문제에서는 정렬 후에 카메라를 최소로 설치 할 수 있는 방법을 고민하면 될 거 같습니다.

 

일단 문제에서 나오는 -20, -15의 경우 -20가 진입, -15가 진출이므로 -20 ~ -15는 운행을 한다는 의미로 생각할 수 있습니다.

즉 0번째 차는 -20, -19, -18, -17, -16, -15 구간에 카메라가 있다면 만나게 되는 것이죠.

 

때문에 진출 구간 기준으로 정렬을 해주고, 제일 처음 만나는 진출 구간인 -15를 저장을 합니다. 그리고 -15가 다음 차량이 구간하는 사이에 존재한다면 카메라를 새로 설치할 필요가 없습니다.

 

public class CrackdownCamera {
    public int solution(int[][] routes) {
        Arrays.sort(routes, (o1, o2) -> {
            Integer a = o1[1];
            Integer b = o2[1];
            return a.compareTo(b);
        });

        int answer = 1;
        int camera = routes[0][1];

        for (int i = 1; i < routes.length; i++) {
            int[] route = routes[i];

            if (route[0] <= camera && camera <= route[1]) {
                continue;
            }

            camera = route[1];
            answer++;
        }

        return answer;
    }
}