[알고리즘 문제] 탐욕법 - 프로그래머스 단속 카메라(level 3)

문제 이해

각 차량의 경로는 진입 지점과 진출 지점으로 이루어진 닫힌 구간 [start, end]입니다. 카메라가 구간 안에 있으면 해당 차량을 단속할 수 있으며, 진입점이나 진출점에 설치해도 포함됩니다.

차량 경로: [start, end]
단속 조건: start <= camera <= end

결국 모든 구간을 적어도 한 번 찌르는 점을 최소 개수로 고르는 문제입니다. 어떤 구간을 먼저 처리하고 그 안의 어느 위치를 고를지가 핵심입니다.

탐욕적 선택 찾기

진출 지점이 가장 빠른 차량을 먼저 생각하면 반드시 처리해야 할 대상이 분명해집니다.

1. 이 차량은 진출 지점을 지나면 다시 만날 수 없으므로, 카메라 하나가 반드시 현재 구간 안에 있어야 합니다.
2. 구간 안에서 가장 오른쪽인 진출 지점에 설치하면 현재 차량을 단속하면서 뒤에 오는 구간과 겹칠 가능성을 가장 크게 남깁니다.
3. 따라서 차량을 진출 지점 기준 오름차순으로 정렬하고, 아직 단속되지 않은 첫 차량의 진출 지점에 카메라를 설치합니다.

1. routes를 end 기준 오름차순 정렬
2. 현재 카메라를 포함하지 않는 첫 구간을 찾음
3. 그 구간의 end에 새 카메라 설치
4. 모든 구간을 확인할 때까지 반복

선택이 최적인 이유

진출 지점이 가장 빠른 구간을 A = [start, end]라고 하겠습니다. 어떤 최적해도 A를 단속하려면 그 안의 위치 p에 카메라 하나를 두어야 합니다.

이 카메라를 p에서 A.end로 옮겨도 손해가 없습니다. 정렬상 아직 처리할 구간 B는 A.end <= B.end를 만족합니다. 기존 카메라 p가 B에도 포함되었다면 B.start <= p <= A.end이고, 따라서 A.end 역시 B 안에 있습니다.

즉, 첫 카메라를 가장 빠른 진출 지점에 둔 최적해가 항상 하나 이상 존재합니다. 이 선택 뒤에 남은 구간에도 같은 논리를 반복할 수 있으므로 탐욕법이 전체 최적해를 만듭니다.

첫 구현과 병목

처음에는 설치한 카메라를 벡터에 모두 저장하고, 각 차량이 기존 카메라 중 하나를 포함하는지 전부 검사했습니다. 탐욕적 선택 자체는 맞지만 차량마다 카메라 목록을 다시 순회하므로 최악에는 O(N²)이 됩니다.

vector<int> cameras;

for (const vector<int>& route : routes) {
    bool covered = false;

    for (int camera : cameras) {
        if (route[0] <= camera && camera <= route[1]) {
            covered = true;
            break;
        }
    }

    if (!covered) {
        cameras.push_back(route[1]);
    }
}

차량 수가 최대 10,000대이므로 정렬로 만든 규칙을 이용해 이 중첩 검사를 없애는 편이 좋습니다.

마지막 카메라만 확인하기

카메라는 처리 순서에 따라 항상 오른쪽으로 이동합니다. 새 카메라는 현재 미처리 차량의 진출 지점에 설치되고, 이후 차량의 진출 지점은 이보다 작지 않기 때문입니다. 따라서 과거의 모든 카메라를 저장할 필요 없이 가장 최근에 설치한 카메라 위치만 기억하면 됩니다.

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

camera < route[0]이면 마지막 카메라가 현재 차량의 진입점보다 왼쪽에 있어 이 차량을 단속하지 못합니다. 반대로 이 조건이 거짓이면 정렬 특성상 camera <= route[1]도 보장되므로 카메라는 현재 구간 안에 있습니다.

예제로 따라가기

입력 구간을 진출 지점 기준으로 정렬하면 다음 순서가 됩니다.

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

1. [-20, -15]는 아직 단속되지 않았으므로 -15에 첫 카메라를 설치합니다.
2. [-18, -13]은 -15를 포함하므로 같은 카메라로 처리됩니다.
3. [-14, -5]의 진입점은 -15보다 오른쪽이므로 -5에 두 번째 카메라를 설치합니다.
4. [-5, -3]은 경계값 -5를 포함하므로 추가 설치가 필요 없습니다.

모든 차량을 단속하는 최소 카메라 수는 2입니다.

최종 코드

#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int solution(vector<vector<int>> routes) {
    sort(routes.begin(), routes.end(),
         [](const vector<int>& a, const vector<int>& b) {
             return a[1] < b[1];
         });

    int answer = 0;
    int camera = INT_MIN;

    for (const vector<int>& route : routes) {
        if (camera < route[0]) {
            camera = route[1];
            ++answer;
        }
    }

    return answer;
}

camera를 입력 범위보다 작은 INT_MIN으로 초기화해 첫 차량에서는 반드시 카메라가 설치되도록 했습니다. 차량의 진입·진출 지점은 모두 int 범위 안이므로 안전합니다.

복잡도와 주의점

• 시간복잡도는 O(N log N)
• 진출 지점 기준 정렬이 O(N log N), 정렬 뒤 한 번의 순회가 O(N)입니다.
• 추가 공간은 O(1)
• 정렬 구현의 내부 공간을 제외하면 카메라 위치와 개수만 저장합니다. 별도의 카메라 목록은 필요하지 않습니다.
• 진출 지점을 기준으로 정렬한다
• 진입 지점 기준 정렬만으로는 가장 먼저 놓칠 차량과 카메라의 최적 위치를 바로 결정할 수 없습니다.
• 경계값도 단속에 포함한다
• 진입점에 카메라가 있어도 단속되므로 새 카메라 조건은 camera < route[0]입니다. <=를 사용하면 불필요한 카메라가 추가됩니다.

정리

• 차량 경로를 닫힌 구간으로 보고 모든 구간을 찌르는 최소 개수의 점을 찾는다.
• 진출 지점이 가장 빠른 차량은 더 늦기 전에 반드시 처리해야 한다.
• 현재 차량의 진출 지점에 카메라를 두면 이후 구간을 포함할 가능성을 가장 크게 남긴다.
• 교환 논증으로 임의의 최적해의 첫 카메라를 이 위치로 옮겨도 손해가 없음을 확인할 수 있다.
• 정렬 뒤에는 마지막 카메라 하나만 확인해 전체 풀이를 O(N log N)에 끝낸다.

이번 풀이에서는 탐욕적 선택을 찾는 것만큼, 정렬이 만들어 낸 순서를 끝까지 활용하는 것이 중요했습니다. 선택은 맞았지만 모든 카메라를 재검사하던 초안을 개선하면서 탐욕법의 간결함과 효율을 코드에도 그대로 반영할 수 있었습니다.