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

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

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

---

 

풀이

1. 자동차가 나가는 지점을 기준으로 오름차순으로 정렬을 한다.

2. 정렬후 첫번째 자동차가 나간 지점을 checkPoint(카메라 지점)로 설정을 한다.

3. 다음 자동차를 탐색하면서, 이 자동차가 checkPoint에 포함이 되어있으면 만난다는 뜻이므로 넘겨준다

4. 만약 checkPoint에 포함이 되지않는다면, 즉 이전에 설치한 카메라에 걸리지 않는다면 새로운 카메라를 나가는 지점에 설치해준 뒤, 카메라의 개수를 갱신해준다.

 

시간복잡도

routes의 개수를 N이라고 한다면, 정렬에 O(NlogN)시간이 걸리고, 카메라의 개수를 구하는것은 O(N)이 걸리므로, O(N)이 된다. 따라서 O(NlogN)이 된다.

 

코드

import java.util.Arrays;
class Solution {
    public int solution(int[][] routes) {
        int answer=0;
			
            //나가는 지점을 기준으로 오름차순 정렬
            Arrays.sort(routes, (o1,o2)->{
                if(o1[1]==o2[1]){
                    return Integer.compare(o1[0],o2[0]);
                }
                else{
                    return Integer.compare(o1[1],o2[1]);
                }
            });
            int checkPoint=routes[0][1];
            answer++;
            for(int i=1;i<routes.length;i++){
                if(checkPoint<routes[i][0]){
                    answer++;
                    checkPoint=routes[i][1];
                }
            }
            return answer;
    }
}