[Python/Programmers] 단속카메라

문제

1. 문제 난이도: 프로그래머스 Lv.3

2. 문제 요약

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

제한사항

• 차량의 대수는 1대 이상 10,000대 이하입니다.
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

입력 예시
[[-20,-15], [-14,-5], [-18,-13], [-5,-3]]

3. 문제 핵심

내 코드

1. 1차 시도(틀린 코드)

from collections import deque

def solution(routes):
    routes.sort()
    queue = deque(routes)
    visited = [False] * len(routes)
    
    enter, exit = queue.pop left()
    answer = 1
    
    while queue:
        q = queue.popleft()
        if q[0]>exit:
            answer +=1
            exit = q[1]
    return answer

• 문제의 테스트 케이스: [[-7,0], [-6,-4], [-5,-3], [-3,-1], [-1,4], [1,2], [3,4]]
  - queue -> deque([[-7, 0], [-6, -4], [-5, -3], [-3, -1], [-1, 4], [1, 2], [3, 4]])
  - 위의 코드 따르면: 0, 1, 4에 3개
  - 하지만 0초에 카메라를 두면 [-6, -4], [-5,-3], [-3. -1]은 안찍힘(0초에 진입하지도 않았으니까)

2. 2차 시도

def solution(routes):
    routes.sort(key=lambda x:x[1])
    
    camera = routes[0][1]
    answer = 1 
    for route in routes:
        if route[0] > camera:
            camera = route[1]
            answer +=1
    
    return answer

• 가장 중요한 것은 exit 시점 (enter < exit이므로)
• 문제의 테스트 케이스에 대해
  정렬 이후 routes : [[-6, -4], [-5, -3], [-3, -1], [-7, 0], [1, 2], [-1, 4], [3, 4]]
  -> -4, -1, 2, 4초 -> 4군데 카메라 설치