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

오랜만에 문제를 읽고 어떻게 풀어야 하는지 감이 오지 않았다.

문제 유형이 그리디로 분류되어 있었지만, 로직 자체가 생각나지 않았다.

결국 고민하다가 검색을 통해서 힌트를 얻었다.

---

로직

이 문제의 키포인트는 정렬이다.

각 자동차의 진출 시간인 routes [i][1] 값을 기준으로 정렬하면 문제를 쉽게 해결할 수 있다.

왜냐하면 n번째 자동차의 진출시간과 n+1 자동차의 진입시간을 비교해 n+1번째 자동차의 진입시간이 n번째 자동차의 진출 시간 이전이라면 카메라의 숫자를 늘릴필요가 없어 다음 차량으로 넘어가면 되고, n+1번째 자동차의 진입시간이 n번째 자동차의 진출 시간 이후라면 min의 값을 바꾸고 카메라의 숫자를 +1 하면 되기 때문이다. 

 

최종 코드

import java.util.*;
class Solution {
    public int solution(int[][] routes) {
        int answer = 0;
        // routes[1] 값을 기준으로 오름차순 정렬
        Arrays.sort(routes, Comparator.comparingInt(a -> a[1]));

        int min = Integer.MIN_VALUE;

        // 현재 자동차의 진입시간이 이전 자동차의 진출시간보다 뒤라면
        for (int i = 0; i < routes.length; i++) {
            if(routes[i][0] > min) {
                min = routes[i][1];
                answer++;
            }
        }

        return answer;
    }
}