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

https://programmers.co.kr/learn/courses/30/lessons/42884

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

 

 

어려워보이지만 조금만 쉽게 생각해보면 간단히 풀리는 문제였다.

 

문제를 요약하자면 N대의 자동차가 어느 도로 위를 주행한다. 각 차마다 그 도로에 진입하는 지점과 도로에서 나가는 지점이 주어진다. 이 도로에 진입하여 주행하는 차들은 적어도 한 번은 단속카메라를 거쳐야 하는데 단속카메라를 최소한의 개수로 설치하여 모든 차가 단속카메라를 거치게 하고 싶다. 이때 필요한 카메라의 개수를 구하는 문제이다.

 

상식적으로 생각했을때 도로 위에 자동차가 가장 많는 지점에 카메라를 설치하는게 이상적일 것이다.

이 생각을 전제로 깔아두고 다음 단계로 넘어가자.

 

단순하게 한 자동차 입장에서 생각해보자. 문제 조건에 따르면 모든 자동차는 도로 위를 주행하는 동안 한 번은 카메라를 거쳐야한다.

그렇다면 언제 카메라에 찍히는게 가장 합리적일까? 어느 자동차이던 도로를 나가기 직전에 카메라를 거치는 것이 합리적이다.

그 이유는 최대한 많은 차들이 카메라에 찍힐 수 있도록 도로에 들어올때까지 기다려야하기 때문이다.

그래서 카메라를 설치하는 지점은 N대의 자동차 중에서 어느 차가 나가는 지점이 된다.

 

N대의 자동차를 도로에서 나가는 지점을 기준으로 오름차순 정렬하여 도로에서 가장 먼저 나가는 자동차부터 하나씩 확인한다.

처음으로 나가는 자동차는 아직 도로에 설치된 카메라가 없으므로 그 차가 나가는 지점에 카메라를 설치할 것이다.

 

그 다음으로 도로에서 나가는 자동차를 확인하자. 이미 카메라에 찍힌 자동차라면 이 차가 나가는 지점에 카메라를 설치할 필요가 없다.

현재 확인하는 차가 카메라에 찍혔는지 확인할 수 있는 방법은 가장 최근에 설치된 카메라의 지점과 그 차의 진입 지점을 확인하는 것이다.

카메라가 설치된 지점보다 이후에 도로에 진입했다면 카메라에 찍히지 않았으므로 도로에서 나가는 지점에 카메라를 설치하고 최근 설치한 카메라 위치를 갱신한다.

 

def solution(routes):
    answer = 0
    routes = sorted(routes, key=lambda x: x[1])
    camera = -30001
    
    for start, end in routes:
        if camera < start:
            answer += 1
            camera = end
    
    return answer