[프로그래머스] 단속 카메라 (그리디)

문제 소개

 

단속 카메라 - 프로그래머스 문제를 정리합니다.
이 문제는 모든 차량이 최소 한 번 단속 카메라를 지나도록 하기 위해 카메라를 최소 몇 대 설치해야 하는지 구하는 최소 지점 커버 문제입니다.
핵심은 차량 경로의 겹침 구간을 고려해 가장 빠른 진출 지점 위주로 카메라를 설치하는 전략입니다.

문제 링크: 단속 카메라 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 차량의 진출 지점을 기준으로 정렬
2. 이미 설치된 카메라 위치로 차량이 단속되는지 확인
   단속되지 않는 경우, 해당 차량의 진출 지점에 새로운 카메라 설치
3. 진출 입구에 설치하면 지나가는/진출하는 차량 등 최대한 많은 차량 커버 가능 → 탐욕적 선택 (Greedy)

---

해결 과정 및 코드

핵심 아이디어

1. 차량 경로를 진출 지점 기준으로 오름차순 정렬
2. 현재 차량의 진입 지점이 이전에 설치된 카메라 위치보다 크다면, 기존 카메라에 안 걸리는 것 → 새로 설치

코드

시간 복잡도 : O(N log N) ( 정렬 N log N + 배열 순회 N )

import java.util.*;

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

        int camera = Integer.MIN_VALUE; // 마지막으로 설치한 카메라 위치
        int count = 0; // 설치한 카메라 개수
        
        for (int[] route : routes) {
            int entry = route[0];
            int exit = route[1];

            // 현재 차량의 진입 지점이 기존 카메라보다 뒤에 있으면 단속 못 함 → 새로 설치
            if (camera < entry) {
                camera = exit;  // 진출 지점에 설치
                count++;
            }
        }

        return count;
    }
}

 

드디어 프로그래머스 알고리즘고득점 Kit를 다 정리했네요 !