[Programmers] 단속카메라 - [탐욕법(Greedy)]

[Programmers] 단속카메라 - [탐욕법(Greedy)]

문제 링크

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

문제 요약

고속도로를 이용하는 차량들의 진입/진출 지점이 주어질 때, 모든 차량이 최소 한 번은 카메라를 만나도록 설치해야 하는 최소 카메라 개수를 구하는 문제.

접근 방법

• 자료구조: std::vector<vector<int>> (차량 경로 저장)
• 알고리즘: 탐욕법 (Greedy Algorithm)
• 핵심 아이디어: 1. 차량을 진출 지점 기준으로 오름차순 정렬한다. 2. 가장 먼저 나가는 차량의 진출 지점에 카메라를 설치한다. 3. 다음 차량의 진입 지점이 현재 카메라 위치보다 뒤에 있다면, 해당 차량의 진출 지점에 새로운 카메라를 설치한다.

풀이 코드

#include <vector>
#include <algorithm>

using namespace std;

// 진출 지점 기준 오름차순 정렬을 위한 비교 함수
bool compare(const vector<int>& a, const vector<int>& b) {
    return a[1] < b[1];
}

int solution(vector<vector<int>> routes) {
    int answer = 0;
    
    // 1. 진출 지점 기준으로 정렬 (Greedy 핵심)
    sort(routes.begin(), routes.end(), compare);
    
    // 마지막으로 설치된 카메라의 위치 (초기값은 가능한 최소 범위보다 작게 설정)
    int last_camera = -30001;
    
    for (const auto& route : routes) {
        // 2. 현재 차량의 진입 지점이 마지막 카메라 위치보다 뒤에 있다면
        if (last_camera < route[0]) {
            // 카메라를 새로 설치하고 위치를 현재 차량의 진출 지점으로 갱신
            answer++;
            last_camera = route[1];
        }
    }
    
    return answer;
}

시간/공간 복잡도

• 시간 복잡도: $O(N \log N)$ (정렬 시 $N \log N$, 이후 벡터를 1회 순회하므로 $N$. 전체적으로 정렬이 지배함)
• 공간 복잡도: $O(1)$ 또는 $O(\log N)$ (입력 배열 외에 추가 공간 사용은 미미하며, 정렬 알고리즘의 스택 공간 정도 사용)

실행 결과

• 정확성 테스트: 통과
• 효율성 테스트: 통과 (최대 10,000대 기준 매우 빠른 속도)

핵심 포인트

1. 정렬 기준의 선택: 진입 지점이 아닌 '진출 지점'을 기준으로 정렬해야 현재 선택한 카메라가 다음 차량들을 최대한 많이 포함할 수 있는 가능성이 커집니다.
2. 카메라 위치 갱신: 새로운 카메라가 필요할 때마다 그 차량의 가장 끝 지점(진출 지점)에 설치함으로써 이후 차량들과 겹칠 확률을 극대화합니다.

예제 확인

• 예제 1: [[-20,-15], [-14,-5], [-18,-13], [-5,-3]]
  • 정렬 후: [[-20,-15], [-18,-13], [-14,-5], [-5,-3]]
  • 1번 차량 진출(-15)에 설치 → 2번 차량 진입(-18)이 -15보다 앞이므로 패스.
  • 3번 차량 진입(-14)이 -15보다 뒤이므로 3번 진출(-5)에 새로 설치.
  • 4번 차량 진입(-5)이 -5와 같으므로 패스.
  • 결과: 2개