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

문체 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42884
난이도 : Level 3

문제 요약

고속도로를 이동하는 차량의 이동 경로가 다음과 같이 주어진다.

routes = [
    [진입 지점, 진출 지점],
    [진입 지점, 진출 지점],
]

모든 차량이 최소 한 번은 단속카메라를 만나도록 카메라를 설치할 때, 필요한 카메라의 최소 개수를 구하는 문제다.

예를 들어 다음과 같은 차량 경로가 있다고 하자.

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

각 차량의 이동 구간이 겹치는 지점(-15, -5) 에 카메라를 설치하면 여러 차량을 한 번에 단속할 수 있다.

---

풀이 아이디어

어차피 모든 차량은 최소 한 번 이상 카메라에 찍혀야 한다.
따라서 가장 먼저 진출하는 차량은 반드시 진출하기 전까지 카메라를 만나야 한다.

이 차량을 최대한 늦게 단속하면서 다른 차량까지 함께 단속하려면, 해당 차량이 나가는, 진출지점에 카메라를 설치하는 것이 가장 유리하다.

이후 그 지점을 지나가는 차량들은 같은 카메라로 함께 단속할 수 있으므로 제거하고, 남은 차량들에 대해 같은 과정을 반복한다.

---

차량의 진출 지점이 빠른 순서대로 정렬한다.

routes.sort(key=lambda x: x[1])

예시 데이터를 진출 지점 기준으로 정렬하면 다음과 같다.

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

가장 먼저 진출하는 차량의 진출 지점에 카메라를 설치한다.

첫 번째 차량의 진출 지점은 -15이므로 카메라 위치는 다음과 같다.

pointer = -15

그다음 모든 차량을 확인하면서 -15를 지나가는 차량을 찾는다.

start <= pointer <= end

카메라 위치를 포함하는 차량들은 모두 해당 카메라에 단속되므로 리스트에서 제거한다.

이 과정을 차량이 모두 사라질 때까지 반복한다.

---

전체 코드

def solution(routes):
    
    count = 0
    
    def isInRange(num, start, end):
        return start <= num <= end
    
    # 진출 지점이 빠른 순서대로 정렬
    routes.sort(key=lambda x: x[1])
    
    while routes:
        
        # 가장 먼저 진출하는 차량의 진출 지점에 카메라 설치
        pointer = routes[0][1]
        
        # 해당 카메라 위치를 포함하는 차량의 인덱스를 저장
        idxs = []
        
        for i, route in enumerate(routes):
            if isInRange(pointer, route[0], route[1]):
                idxs.append(i)
        
        # 인덱스가 밀리지 않도록 뒤에서부터 삭제
        for i in sorted(idxs, reverse=True):
            del routes[i]
        
        count += 1
        
    return count

---

시간 복잡도 비교

내 풀이에서는 카메라 위치를 정한 뒤, 해당 카메라에 찍히는 차량들의 인덱스를 모아서 routes 리스트에서 직접 삭제했다.

while routes:
    pointer = routes[0][1]

    idxs = []

    for i, route in enumerate(routes):
        if isInRange(pointer, route[0], route[1]):
            idxs.append(i)

    for i in sorted(idxs, reverse=True):
        del routes[i]

    count += 1

이 방식은 한 번의 반복마다 남아 있는 차량들을 다시 확인한다.

또한 파이썬 리스트에서 중간 요소를 삭제하면 뒤에 있는 요소들을 앞으로 당기는 작업이 발생한다.

따라서 최악의 경우 시간 복잡도는 다음과 같다.

O(N²)

문제의 제한에서는 통과할 수 있지만, 차량 수가 많아지면 비효율적일 수 있다.

---

더 나은 풀이는 차량을 리스트에서 삭제하지 않고, 진출 지점을 기준으로 정렬한 뒤 한 번만 순회하는 방식이다.

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

    count = 0
    camera = -30001

    for start, end in routes:
        if start > camera:
            camera = end
            count += 1

    return count

현재 차량의 진입 지점이 기존 카메라 위치보다 크다면, 기존 카메라로는 해당 차량을 찍을 수 없다.

if start > camera:

이때만 현재 차량의 진출 지점에 새로운 카메라를 설치한다.

반대로 현재 차량의 진입 지점이 카메라 위치보다 작거나 같다면, 이미 설치된 카메라가 차량의 이동 구간 안에 있으므로 추가로 설치하지 않는다.

이 방식의 시간 복잡도는 다음과 같다.

• 진출 지점 기준 정렬: O(N log N)
• 전체 차량 순회: O(N)

따라서 최종 시간 복잡도는 다음과 같다.

O(N log N)

정리하면 내 풀이는 단속된 차량을 직접 삭제하면서 다시 탐색하기 때문에 O(N²)이고, 더 나은 풀이는 정렬 후 한 번만 순회하므로 O(N log N)이다.

---

파이썬 리스트 요소 제거 방법

파이썬에서 리스트의 요소를 제거할 때는 del, remove(), pop(), clear() 등을 사용할 수 있다.

---

1. del

특정 인덱스의 요소를 삭제할 때 사용한다.

numbers = [10, 20, 30, 40]

del numbers[1]

print(numbers)
# [10, 30, 40]

범위를 지정해서 여러 요소를 삭제할 수도 있다.

numbers = [10, 20, 30, 40, 50]

del numbers[1:3]

print(numbers)
# [10, 40, 50]

del은 삭제한 값을 반환하지 않는다.

---

2. remove()

특정 값을 찾아 삭제할 때 사용한다.

numbers = [10, 20, 30, 20]

numbers.remove(20)

print(numbers)
# [10, 30, 20]

동일한 값이 여러 개 있다면 가장 앞에 있는 값 하나만 삭제한다.

삭제하려는 값이 리스트에 없다면 ValueError가 발생한다.

numbers = [10, 20, 30]

numbers.remove(40)
# ValueError

오류를 피하려면 값이 존재하는지 먼저 확인할 수 있다.

numbers = [10, 20, 30]

if 40 in numbers:
    numbers.remove(40)

---

3. pop()

특정 인덱스의 요소를 삭제하면서 삭제된 값을 반환한다.

numbers = [10, 20, 30]

removed_number = numbers.pop(1)

print(removed_number)
# 20

print(numbers)
# [10, 30]

인덱스를 작성하지 않으면 마지막 요소를 삭제한다.

numbers = [10, 20, 30]

removed_number = numbers.pop()

print(removed_number)
# 30

print(numbers)
# [10, 20]

삭제한 값을 이후에 사용해야 할 때 유용하다.

---

4. clear()

리스트의 모든 요소를 삭제한다.

numbers = [10, 20, 30]

numbers.clear()

print(numbers)
# []

리스트 자체는 유지하고 내부 요소만 모두 제거한다.

---

여러 인덱스를 삭제할 때 주의할 점

리스트에서 요소를 삭제하면 뒤에 있던 요소들의 인덱스가 앞으로 당겨진다.

다음 리스트에서 인덱스 1과 3을 삭제한다고 해보자.

numbers = [10, 20, 30, 40, 50]
idxs = [1, 3]

인덱스 1을 먼저 삭제하면 리스트가 다음과 같이 변경된다.

[10, 30, 40, 50]

원래 인덱스 3에 있던 40은 인덱스 2로 이동한다.

이 상태에서 인덱스 3을 삭제하면 원래 삭제하려던 40이 아니라 50이 삭제된다.

따라서 여러 인덱스를 삭제할 때는 인덱스를 내림차순으로 정렬한 뒤, 뒤쪽 요소부터 삭제해야 한다.

numbers = [10, 20, 30, 40, 50]
idxs = [1, 3]

for i in sorted(idxs, reverse=True):
    del numbers[i]

print(numbers)
# [10, 30, 50]

이번 단속카메라 풀이에서도 같은 방식으로 차량을 제거했다.

for i in sorted(idxs, reverse=True):
    del routes[i]

뒤쪽 요소부터 삭제하면 앞쪽 요소의 인덱스에는 영향을 주지 않기 때문에 안전하게 삭제할 수 있다.

---

리스트 삭제 방법 정리

문법	삭제 기준	삭제한 값 반환	특징
del list[index]	인덱스	X	특정 인덱스 또는 범위 삭제
list.remove(value)	값	X	일치하는 첫 번째 값 삭제
list.pop(index)	인덱스	O	삭제한 값을 사용할 수 있음
list.clear()	전체	X	리스트의 모든 요소 삭제

---

마무리

이 문제의 핵심은 가장 먼저 진출하는 차량의 진출 지점에 카메라를 설치하는 것이다.

진출 지점을 기준으로 정렬한 뒤, 해당 카메라를 지나가는 차량을 한 번에 제거하는 방식으로 해결했다.

또한 리스트에서 여러 요소를 삭제할 때는 인덱스가 변경될 수 있으므로 반드시 뒤쪽 인덱스부터 삭제해야 한다.