[42884] 단속카메라

✔ 단속카메라

[프로그래머스 42884]

문제 분석하기

차량의 이동 경로를 나간 시점을 기준으로 오름차순 해준 후, 같은 카메라를 사용할 수 있는지 확인

예) [-20, -15], [-18, -13], [-14, -5], [-5, -3]

i	camera	같은 카메라를 사용할 수 있는지	answer
0	-15		1([-20, -15])
0	-15	-15는 -18과 -13 사이	1([-20, -15], [-18, -13])
2	-15	-15는 -14과 -5 사이가 아님	2 ([-20, -15], [-18, -13] / [-14, -5])
2	-5	-5는 -5과 -3 사이	2 ([-20, -15], [-18, -13] / [-14, -5], [-5, -3])

손으로 풀어보기

1. 차량의 이동 경로를 나간 시점을 기준으로 오름차순 정렬
2. 맨 앞 차량부터 시작하여 반복문으로 탐색하며 같은 카메라를 사용할 수 있는지 확인
   
   • 현재 카메라의 위치(현재 차량의 나간 지점)가 다음 차량의 진입 지점보다 작을 경우 같은 카메라 사용 불가
3. 카메라 갯수 반환

슈도코드 작성하기

routes(차량의 경로)
answer(카메라의 최소 설치 갯수)
routes 나간 지점을 기준으로 오름차순 정렬
camera(현재 카메라 위치)
for(routes만큼) {
    if (현재 카메라의 위치가 route의 진입 지점보다 작으면) {
        현재 카메라 위치를 새로운 카메라 위치로 변경
        카메라 갯수 증가
    }
}
answer 반환

코드 구현하기

/**
 * 42884) 단속카메라
 */
public class K006_42884 {
    // routes(차량의 경로)
    public int solution(int[][] routes) {
        // answer(카메라의 최소 설치 갯수)
        int answer = 0;
        // routes 나간 지점을 기준으로 오름차순 정렬
        // Arrays.sort(routes, (r1, r2) -> Integer.compare(r1[1], r2[1]));
        Arrays.sort(routes, new Comparator<int[]>() {
            @Override
            public int compare(int[] route1, int[] route2) {
                return route1[1] - route2[1];
            }
        });
        // camera(현재 카메라 위치)
        int camera = Integer.MIN_VALUE;
        for (int[] route : routes) {
            // 현재 카메라의 위치가 route의 진입 지점보다 작으면
            if (camera < route[0]) {
                // 현재 카메라 위치를 새로운 카메라 위치로 변경
                camera = route[1];
                // 카메라 갯수 증가
                answer++;
            }
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        K006_42884 solution = new K006_42884();

        int[][] routes = { { -20, -15 }, { -14, -5 }, { -18, -13 }, { -5, -3 } };

        int result = solution.solution(routes);

        System.out.println(result);
    }
}