문제 조건

input

• 차량의 진입, 탈출 시점의 좌표 배열 routes
  • 1 ≤ routes ≤ 10,000
  • -30,000 ≤ routes[i] ≤ 30,000

output

• 카메라 개수 n

문제 해석

• 그리디
  • 시간 복잡도 O(nlogn)
  • 탈출 시점을 기준으로 routes 오름차순 정렬
    • 탈출 시점을 기준으로 정렬하는 이유는 카메라 숫자를 최소화하기 위함
    • 다음 진입이 마지막 카메라 위치보다 작을 경우, 이전 카메라로 무조건 단속 가능
    • [[-20, -15], [-18, -13], [-14, -5], [-5, -3]]
  • routes를 순회하면서 진입 시점이 마지막 카메라 위치 보다 앞설 경우
    • 새로운 카메라를 설치해야 됨
    • 새로운 카메라 설치 시 last_camera 변수 갱신

코드

def solution(routes):
    routes.sort(key=lambda x : x[1])
    cnt = 0
    last_camera = -30001 # 문제 조건
    
    for route in routes:
        # 진입 시점과 마지막 카메라 위치 비교
        if route[0] > last_camera:
            cnt += 1
            last_camera = route[1]
            
    return cnt