42884. 단속 카메라

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42884?language=java

제한 사항

풀이

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        int answer = 0;
        
        Arrays.sort(routes, 
                   (r1, r2) -> r1[1] - r2[1]);
        
        int camara = -30001;
        
        for(int i = 0 ; i < routes.length; i++) {
            if(camara < routes[i][0]) {
                camara = routes[i][1];
                answer++;
            }
        }
        return answer;
    }
}

회고

막상 구현은 간단한데 아이디어가 쉽게 떠오르지 않은 문제였다. 존재하지 않는 위치에 임의로 카메라를 두고(-30001) 풀면 생각에 도움이 된다. 제한 사항을 잘 읽어야 겠다는 생각을 했다. 괜히 진출 지점을 -30,000~30,000을 두는게 아닌 것 같다.

 

우선, 진출 지점을 기준으로 오름차순 정렬을 수행한다. 그리고 카메라 위치 기준 각 루트의 진입 지점이 카메라 위치보다 앞에 있으면, 진입과 진출 사이에 카메라에 걸릴 것이다. 반대로 카메라 위치보다 뒤에 있으면, 카메라에 걸리지 않으므로 새 카메라를 설치해야한다.

새 카메라 위치를 어디에 두느냐가 관건이었다. 새 카메라 위치는 루트의 진출 지점에 둬야 최소한 진입 지점에서 진출 지점 사이에 진입하는 새 루트가 카메라에 걸릴 것이다.