[Lv.3] 프로그래머스 - 단속카메라 : Java

프로그래머스

 

 

 

이해하기

{{-20, -15}, {-14, -5}, {-18, -13}, {-5, -3}} 을 진출 지점을 기준으로 정렬한다.

 

첫번째 줄의 진출 지점에 일단 카메라를 설치한다.

-15 지점에 카메라를 설치하면 두번째 줄까지 커버 가능하기에 두번째 줄에는 카메라를 설치할 필요가 없다.

세번째 줄은 커버되지 않으므로 진출 지점에 카메라를 설치한다.

-5 지점에 카메라를 설치하면 네번째 줄까지 커버 가능하기에 네번째 줄에는 카메라를 설치할 필요가 없으니 총 2대만 설치하면 된다.

 

 

문제풀이

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        int answer = 0;
        int cam = Integer.MIN_VALUE;

        Arrays.sort(routes, (o1, o2) -> o1[1] - o2[1]);

        for (int[] route : routes) {
            if (cam < route[0]) {
                cam = route[1];
                answer++;
            }
        }

        return answer;
    }
}

 

            if (cam < route[0]) {
                cam = route[1];
                answer++;
            }

 

이 부분은 캠이 마지막으로 설치된 지점과 이번 줄의 진입 지점을 비교하는 것이다.

예를 들어 마지막으로 캠이 설치된 지점이 -15이고, 이번에 살펴야 할 줄이 {-14, -5}라면 진입 지점보다 캠이 왼쪽에 있으니 직전에 설치된 캠으로는 해당 줄을 커버할 수 없다.

그렇기에 cam을 해당 줄의 진출 지점에 설치하고 (cam = route[1]) 카메라 개수를 하나 늘려주는 것이다.