프로그래머스

프로그래머스 단속카메라 풀이: 종료 지점 기준 그리디

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

  • 문제: 단속카메라
  • 출처: 프로그래머스 코딩테스트 연습, 2019 KAKAO BLIND RECRUITMENT
  • 자체 판단 난이도: Level 3

각 차량의 이동 구간을 하나의 구간으로 보고, 모든 구간을 포함하는 지점을 최소 개수로 선택해야 한다. 구간의 끝점을 기준으로 선택하는 그리디 발상이 핵심이며, 끝점이 겹치는 경우까지 정확히 처리해야 하므로 Level 3으로 판단했다.

1. 문제 요약

차량의 진입 지점과 진출 지점이 [진입, 진출] 형태로 주어진다. 카메라는 도로의 한 지점에 설치되고, 차량이 그 지점을 지나가면 단속된다. 모든 차량을 한 번 이상 단속할 수 있도록 필요한 카메라의 최소 개수를 구한다.

차량이 진입 지점 start부터 진출 지점 end까지 이동하므로 카메라 위치 camera가 다음 조건을 만족하면 해당 차량이 단속된다.

start <= camera <= end

즉, 진입점과 진출점도 차량의 이동 구간에 포함된다. 따라서 한 차량의 진출점에 카메라를 설치하는 것이 허용되고, 앞 차량의 진출점과 뒤 차량의 진입점이 같아도 카메라 하나로 두 차량을 단속할 수 있다.

2. 문제 해결에 사용되는 알고리즘

구간을 진출 지점(end) 오름차순으로 정렬한 뒤 왼쪽부터 확인한다. 아직 설치한 카메라에 단속되지 않은 구간을 만나면 그 구간의 진출점에 카메라를 설치한다.

카메라 위치를 last_camera라고 할 때, 현재 구간 [start, end]에 대해 다음과 같이 판단한다.

  • start <= last_camera: 현재 카메라가 구간 안에 있으므로 이미 단속된 차량이다.
  • start > last_camera: 현재 카메라가 구간보다 왼쪽에 있으므로 단속할 수 없다. end에 새 카메라를 설치한다.

가장 빨리 끝나는 경로의 끝에 두어도 최적해를 유지한다

현재까지 처리하지 않은 구간 중 종료 지점이 가장 작은 구간을 R = [s, e]라고 하겠다. 어떤 유효한 배치든 R을 단속하는 카메라 하나는 R 안에 있어야 한다. 그 위치를 p라고 하면 p <= e다. 이 카메라를 e로 옮겨도 R은 여전히 단속된다.

R보다 먼저 끝나는 미처리 구간은 없다. 따라서 p에 있던 카메라가 함께 단속하던 다른 미처리 구간 [a, b]는 a <= p <= e이고 b >= e를 만족한다. p를 e로 옮겨도 이 구간은 계속 포함된다. 그러므로 최적해의 첫 카메라를 e에 두도록 바꿔도 카메라 수는 늘지 않는다. 이 논리를 남은 구간에도 반복할 수 있으므로, 매번 가장 빨리 끝나는 구간의 진출점에 두는 선택이 안전하다.

진입점도 구간에 포함된다

이 문제의 경로는 양 끝점을 포함하므로 판정은 start > last_camera일 때만 새 카메라를 설치하는 형태가 된다. start == last_camera라면 카메라가 차량의 진입점에 정확히 놓인 것이므로 이미 단속된 상태다.

끝점을 제외하는 구간으로 잘못 해석해 start >= last_camera라고 작성하면, 다음과 같은 입력을 불필요한 카메라 두 대로 처리하게 된다.

routes = [[1, 2], [2, 3]]

첫 구간의 종료점 2에 설치한 카메라는 두 번째 구간의 진입점 2에도 놓여 있으므로 정답은 1이다.

시작점이나 입력 순서만으로 선택하면 카메라가 늘 수 있다

각 구간의 시작점에 카메라를 설치하거나, 입력 순서대로 현재 카메라를 결정하면 이후 구간을 최대한 많이 포함한다는 보장이 없다. 예를 들어 다음 입력을 시작점 기준으로 처리하면 첫 구간의 시작점 1에 카메라를 두고 두 번째 구간의 시작점 2에 다시 둘 수 있다.

routes = [[1, 10], [2, 3], [4, 5]]

종료점 기준으로 정렬하면 [2, 3]의 종료점 3에 카메라 하나를 설치하고, [4, 5]는 두 번째 카메라가 필요하지만 [1, 10]도 3에서 함께 단속할 수 있어 정답은 2다. 입력 순서나 시작점만 보고 선택하면 이처럼 넓은 구간을 활용할 기회를 놓칠 수 있다.

3. 문제 해결 코드 (Python)

def solution(routes):
    routes.sort(key=lambda route: route[1])

    cameras = 0
    last_camera = float("-inf")

    for start, end in routes:
        # 시작점이 카메라보다 오른쪽이면 현재 카메라로 잡을 수 없다.
        if start > last_camera:
            last_camera = end
            cameras += 1

    return cameras

routes를 종료점 기준으로 정렬한 뒤, 카메라 위치보다 시작점이 큰 구간에만 새 카메라를 설치한다. start == last_camera인 경우를 통과시키므로 공유 끝점을 카메라 하나로 처리한다. 문제의 함수형 제출 형식에 맞춰 solution(routes)가 카메라 개수를 반환한다.

복잡도

구간 수를 n이라고 하면 정렬에 O(n log n), 정렬된 구간을 한 번 순회하는 데 O(n)이 필요하다. 따라서 전체 시간 복잡도는 O(n log n)이다.

정렬 과정에서 사용하는 공간을 제외하면 카메라 위치와 개수만 저장하므로 추가 공간 복잡도는 O(1)이다. Python의 정렬이 입력을 직접 정렬하므로 입력 복사본까지 만들지는 않는다.

4. 공식 예제 검증

공식 예제 입력을 Python 3에서 실행했다.

입력: [[-20, -15], [-14, -5], [-18, -13], [-5, -3]]
기대 출력: 2
실제 출력: 2
확인 결과: 통과

종료점 순으로 정렬하면 [-20, -15], [-18, -13], [-14, -5], [-5, -3]이다. 첫 카메라는 -15에 설치되고, 마지막 구간은 -15보다 시작점이 작지 않으므로 -3에 두 번째 카메라를 설치한다. -5는 첫 카메라가 잡을 수 있는 구간의 범위 밖이므로 두 번째 카메라가 필요하다.

5. 추가 검증 입력·출력

추가 검증 1: 단일 경로

입력: [[1, 2]]
기대 출력: 1
확인 결과: 통과
검증 목적: 최소한의 경로 하나를 카메라 한 대로 처리하는지 확인

추가 검증 2: 분리된 경로

입력: [[1, 2], [3, 4]]
기대 출력: 2
확인 결과: 통과
검증 목적: 두 구간 사이에 공통 지점이 없으면 카메라를 나누는지 확인

추가 검증 3: 진출점과 진입점 공유

입력: [[1, 2], [2, 3]]
기대 출력: 1
확인 결과: 통과
검증 목적: 양 끝점을 포함하는 조건에서 같은 지점의 카메라를 공유하는지 확인

추가 검증 4: 중복 및 겹치는 경로

입력: [[-5, 0], [-5, 0], [-4, 1], [2, 3]]
기대 출력: 2
확인 결과: 통과
검증 목적: 중복·겹침 구간은 한 카메라로 묶고 떨어진 구간에는 새 카메라를 설치하는지 확인

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 겹치는 구간을 하나의 카메라로 감시하는지 확인할 수 있다.

assert solution([[-20, -15], [-14, -5], [-18, -13], [-5, -3]]) == 2
assert solution([[0, 0]]) == 1

6. 다른 풀이 방식 검색 및 비교

공식 문제도 여러 차량 경로를 지나는 공통 지점의 최소 개수를 묻는다. 참고 자료의 구간 스케줄링처럼 끝점 순으로 정렬해 현재 선택을 최대한 뒤로 미루는 발상을 적용할 수 있다는 점은 같다. 다만 이 글에서는 선택한 지점이 모든 구간을 포함하는지 start <= last_camera로 확인하고, 포함 구간이 아니면 해당 구간의 종료점에 카메라를 설치한다.

마무리

단속카메라 문제에서는 구간을 시작점이 아니라 종료점 기준으로 정렬하는 것이 핵심이다. 가장 먼저 끝나는 경로의 종료점에 카메라를 두면 현재 경로를 놓치지 않으면서 뒤의 경로를 최대한 함께 단속할 수 있다. 양 끝점을 포함한다는 조건까지 반영해 start > camera일 때만 새 카메라를 설치하면 최소 개수를 구할 수 있다.

#그리디#프로그래머스#난이도 3