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

단속카메라

문제링크

풀이

탐욕법(Greedy)
1. routes를 routes[i][1] (i번째 차량이 고속도로에서 나간 지점)을 기준으로 오름차순으로 정렬한다.
2. 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하이므로 초기 단속용 카메라 설치위치(limit)를 -30,001로 설정한다.
3. routes를 순회하면서 단속용 카메라 설치위치(limit)가 현재 route[0]보다 작다면 현재 차량은 단속용 카메라를 한번도 만나지 못한 경우이므로, limit = route[1];로 새롭게 설치하고, 설치 갯수(answer)를 증가한다.

코드

import java.util.*;

class Solution {
    public 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 limit = -30_001;
        for (int[] route : routes) {
            if (route[0] > limit) {
                limit = route[1];
                answer++;
            }
        }

        return answer;
    }
}