[프로그래머스] 단속카메라

문제 요약

각 차량의 고속도로 이동 경로가 구간으로 주어진다. 모든 차량이 적어도 한 대의 카메라를 만나도록 하면서, 설치해야 하는 카메라 수의 최솟값을 구한다.

카메라는 차량의 진입 지점이나 진출 지점에 설치되어 있어도 해당 차량을 단속할 수 있다.

핵심 아이디어

각 차량 경로를 하나의 구간으로 생각한다.

가장 먼저 끝나는 구간의 진출 지점에 카메라를 설치하면, 이 구간은 반드시 단속할 수 있다. 또한 그 위치를 포함하는 뒤의 구간들도 함께 단속할 수 있다.

따라서 진출 지점을 기준으로 오름차순 정렬한 뒤 다음을 반복한다.

1. 아직 단속되지 않은 구간을 만난다.
2. 그 구간의 진출 지점에 카메라를 설치한다.
3. 이후 카메라 위치를 포함하는 모든 구간은 이미 단속된 것으로 처리한다.

왜 진출 지점에 설치할까?

아직 단속되지 않은 경로 중 진출 지점이 가장 이른 차량을 먼저 보자.

이 차량을 단속하려면 카메라는 해당 구간 안에 있어야 한다. 그중 가장 오른쪽인 진출 지점에 카메라를 놓으면, 앞으로 시작하는 다른 경로와 겹칠 가능성이 가장 커진다.

더 왼쪽에 설치하는 것보다 더 많은 경로를 함께 단속할 수 있으므로, 진출 지점 선택이 항상 유리하다.

풀이 과정

1. 각 경로의 시작과 끝을 오름차순으로 정리한다.
2. 끝 지점을 기준으로 경로를 정렬한다.
3. 카메라 위치를 매우 작은 값으로 초기화한다.
4. 현재 경로의 시작 지점이 카메라 위치보다 크다면, 기존 카메라로 단속할 수 없다.
5. 현재 경로의 끝 지점에 새 카메라를 설치한다.
6. 설치한 카메라 수를 반환한다.

Python 코드

def solution(routes):
    # 입력 방향과 무관하게 [시작 지점, 끝 지점] 형태로 정리한다.
    routes = [sorted(route) for route in routes]

    # 가장 빨리 끝나는 경로부터 확인한다.
    routes.sort(key=lambda route: route[1])

    camera_count = 0
    camera_position = -float("inf")

    for start, end in routes:
        # 현재 카메라가 이 차량의 경로 안에 없다면 새 카메라가 필요하다.
        if camera_position < start:
            camera_count += 1
            camera_position = end

    return camera_count

예시

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

진출 지점 기준 정렬 결과는 다음과 같다.

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

• 첫 번째 경로의 끝인 -15에 카메라를 설치한다.
• [-18, -13]은 -15를 포함하므로 단속된다.
• [-14, -5]는 -15를 포함하지 않으므로 -5에 카메라를 설치한다.
• [-5, -3]은 -5를 포함하므로 단속된다.

따라서 필요한 카메라 수는 2대다.

시간 복잡도

N을 차량 수라고 하자.

• 경로 정렬: O(N log N)

• 정렬된 경로 순회: O(N)

• 시간 복잡도: O(N log N)

• 공간 복잡도: O(N)

정리

구간을 최소 개수의 점으로 덮는 문제다. 종료 지점이 가장 이른 구간부터 확인하고, 그 끝에 카메라를 설치하면 최소 개수의 카메라로 모든 차량을 단속할 수 있다.