프로그래머스 단속카메라

프로그래머스 탐욕법 문제 중 하나인 '단속카메라'를 풀면서 겪었던 시행착오와, 그 과정에서 얻게 된 깨달음을 정리하려고 합니다.

처음 문제를 접했을 때 저는 '탐욕법'이라는 키워드를 보고, 자연스럽게 정렬을 떠올렸습니다.
그동안 풀었던 탐욕 문제들 대부분이 정렬 기준만 잘 잡으면 쉽게 풀리는 구조였기 때문입니다.
그래서 별다른 의심 없이 이번 문제도 정렬로 접근했습니다.

진입 시점을 기준으로 오름차순 정렬해보고,
내림차순 정렬도 해보고,진출 시점을 기준으로도 바꿔보면서,정렬 기준만 계속 바꿔가며 답을 찾으려고 했습니다.

그런데 반례가 생기고, 정확한 기준을 잡기가 어려웠습니다.

코드 

def solution(routes):
    routes.sort(key=lambda x: x[1])  
    check = [0] * len(routes)
    ans = 0

    for i in range(len(routes)):
        if check[i]:
            continue
        camera = routes[i][1]
        ans += 1
        check[i] = 1

        for j in range(i+1, len(routes)):
            if routes[j][0] <= camera <= routes[j][1]:
                check[j] = 1

    return ans

1. 차량 정렬

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

우선 차량을 진출 시점 기준 오름차순으로 정렬합니다.
이 정렬이 핵심입니다. 이유는 다음과 같습니다.

• 진출 지점이 빠른 차량을 먼저 처리하면, 해당 차량을 기준으로 가장 많은 차량을 하나의 카메라로 커버할 수 있습니다.
• 즉, 공통 구간의 끝 지점부터 카메라를 설치해 나가면, 중복 없이 최소 카메라 개수로 커버할 수 있게 됩니다.

2. 방문 여부 배열

check = [0] * len(routes)

각 차량이 이미 카메라에 찍혔는지 확인하기 위한 배열입니다.
중복 체크를 방지하기 위해 사용됩니다.

---

3. 차량 반복 처리

for i in range(len(routes)):
    if check[i]:
        continue

이미 찍힌 차량이라면 넘어갑니다.
찍히지 않은 차량이라면, 그 차량을 기준으로 새 카메라를 설치합니다.

---

4. 카메라 설치 및 범위 체크

camera = routes[i][1]
ans += 1
check[i] = 1

현재 차량의 진출 시점에 카메라를 설치합니다.
그 지점은 가장 늦게 차량이 나가는 위치이기 때문에,
다음 차량들이 진입 시점 ≤ 카메라 위치 ≤ 진출 시점인 경우 함께 찍힙니다.

for j in range(i+1, len(routes)):
    if routes[j][0] <= camera <= routes[j][1]:
        check[j] = 1

해당 카메라에 찍히는 차량들을 체크 배열로 표시해둡니다.
이후 다시 돌아왔을 때 이 차량은 건너뛰게 됩니다.

---

5. 반환

return ans

최종적으로 설치한 카메라 개수를 반환합니다.

 

 

• 진출 시점 기준 오름차순 정렬: 가능한 가장 이른 시점에 카메라를 설치해, 최대한 많은 차량을 한 번에 커버하기 위함입니다.
• 방문 체크 방식: 중복 카메라 설치를 방지하기 위해 check 배열을 사용합니다.
• 탐욕적으로 선택: 지금 설치한 카메라로 커버할 수 있는 차량은 모두 커버하고, 다음 안 찍힌 차량부터 다시 새로운 카메라 설치를 시도합니다.

 

 6. 핵심 아이디어

• 차량을 진출 시점 기준 오름차순으로 정렬합니다.
• 가장 먼저 나가는 차량의 진출 지점에 카메라를 설치합니다.
• 이후 이 카메라에 찍히는 차량들을 미리 체크해둡니다.
• 다음 루프에서는 아직 카메라에 안 찍힌 차량만 골라 새로운 카메라를 설치합니다.
• 이 과정을 반복하면 최소 개수의 카메라로 모든 차량을 커버할 수 있습니다.

 7. 입출력 예시 

print(solution([[-20, 15], [-14, -5], [-18, -13], [-5, -3]]))  # 2
print(solution([[-2, -1], [1, 2], [-3, 0]]))  # 2
print(solution([[0, 0]]))  # 1
print(solution([[0, 1], [0, 1], [1, 2]]))  # 1 
print(solution([[0, 1], [2, 3], [4, 5], [6, 7]]))  # 4
print(solution([[-20, -15], [-14, -5], [-18, -13], [-5, -3]]))  # 2
print(solution([[-20, 15], [-20, -15], [-14, -5], [-18, -13], [-5, -3]]))  # 2 
print(solution([[2, 2], [0, 1], [-10, 9]]))  # 2
print(solution([[-7, 0], [-6, -4], [-5, -3], [-3, -1], [-1, 4], [1, 2], [3, 4]]))  # 4
print(solution([[-5, -3], [-4, 0], [-4, -2], [-1, 2], [0, 3], [1, 5], [2, 4]]))  # 2 
print(solution([[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7],[7, 8], [8, 9], [9, 10], [10, 11], [11, 12], [12, 13], [13, 14], [14, 15]]))  # 8
print(solution([[0, 12], [1, 12], [2, 12], [3, 12], [5, 6], [6, 12], [10, 12]]))  # 2 
print(solution([[-191, -107], [-184, -151], [-150, -102], [-171, -124], [-120, -114]]))  # 2