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

문제

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

코딩테스트 연습 - 단속카메라

풀이

Greedy 알고리즘을 이용해서 푼다.

예제 데이터는 아래와 같다.

int[][] route = [[-20,-15], [-14,-5], [-18,-13], [-5,-3]]

route[i][0] = i번 차의 진입 시점

route[i][1] = i번 차의 진출 시점

직관적으로 봤을 때 아래와 같이 카메라를 설치 하면 되는 것을 알 수 있다.

	-20	-19	-18	-17	-16	-15	-14	-13	-12	-11	-10	-9	-8	-7	-6	-5	-4	-3	-2
0	●	●	●	●	●	●
1							●	●	●	●	●	●	●	●	●	●
2			●	●	●	●	●	●
3																●	●	●

 

진출 시점 기준으로 routes를 오름차순해서 다시 그려본다면

	-20	-19	-18	-17	-16	-15	-14	-13	-12	-11	-10	-9	-8	-7	-6	-5	-4	-3	-2
0	●	●	●	●	●	●
1			●	●	●	●	●	●
2							●	●	●	●	●	●	●	●	●	●
3																●	●	●

카메라는 차의 진출 시점에 설치한다. 

이후 차의 진입 시점이 카메라의 설치 지점보다 같거나 앞에 있을 경우, 카메라를 설치할 필요가 없다.

반대로 그 이후 차의 진입 시점이 카메라 설치 지점보다 뒤에 있을 경우, 카메라 설치가 필요하다.

그리고 카메라 설치 지점을 업데이트한다.

위 그래프를 바탕으로 소스코드를 구현하면 아래와 같다. 

 

소스코드

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