프로그래머스: 단속카메라

 

✅ 문제

• 차량의 진입~진출 구간은 범위로 주어집니다.
• 이 범위들이 겹치는 구간을 찾고, 그 구간의 끝부분에 카메라를 설치하면, 겹치는 모든 차량을 한 번에 단속할 수 있어요.
• 겹치지 않는 새로운 구간이 나오면, 새 카메라가 필요합니다.

---

✅ 문제해결 (정렬 + 그리디)

1. 모든 차량 경로를 진출지점 기준으로 정렬
2. 현재 카메라의 설치 위치를 추적 (camera = -30001로 초기화)
3. 각 차량 경로를 보면서, 진입 지점 > camera라면 새로운 카메라 필요

---

JAVA 코드

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        // 1. 차량 경로를 진출지점 기준으로 정렬
        Arrays.sort(routes, (a, b) -> Integer.compare(a[1], b[1]));

        int camera = -30001; // 카메라 설치 위치
        int count = 0;

        for (int[] route : routes) {
            int start = route[0];
            int end = route[1];

            // 현재 카메라가 이 차량 구간을 커버하지 못하면 새로 설치
            if (camera < start) {
                camera = end;
                count++;
            }
        }

        return count;
    }
}

 

 

시간복잡도

• 정렬: O(N log N)
• 순회: O(N)
• 전체: O(N log N) → 매우 효율적!