프로그래머스: 단속카메라

문제

코딩테스트 연습 - 단속카메라

 

문제 풀이

 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하여야 한다. 이때 최소 몇 대의 카메라를 설치해야 하는지 반환하는 문제이다. 처음에 문제를 접하였을 때는 카메라를 만났는지 모든 구간을 확인하며 문제를 풀고자 하였다. 정답은 맞았지만 다른 사람들이 푼 코드를 보니 더 짧고, 빠르게 풀 수 있는 방법이 있었다.😂

 

 설치된 카메라를 진입 지점으로 갱신해 가며, 진입 지점이 설치된 카메라의 위치보다 작다면 카메라를 추가하고 위치를 갱신하면 `O(N)`의 시간으로 문제를 해결할 수 있다.

 

코드

from math import inf


IN, OUT = 0, 1


def solution(routes):
    answer = 0
    routes.sort(key=lambda x: x[OUT])
    camera = -inf

    for route in routes:
        if route[IN] > camera:
            camera = route[OUT]
            answer += 1

    return answer