단속카메라

210711

'''
https://programmers.co.kr/learn/courses/30/lessons/42884
단속카메라
[풀이]
0. O(N^2)과 O(N) 방법이 모두 통과된다. 여기서는 O(N)으로 풀이
1. 자동차의 범위는 -30000부터 30000 이므로 카메라가 존재할 수 있는 위치를 -30001로 설정
=> -30001 부터 30000 까지 증가해 갈 것임
2. Routes를 진출 지점을 기준으로 오름차순으로 정렬
=> 어떤 자동차가 먼저 지나갔는지에 대해 정렬한 것이다.
3. 만약 5초에 진입한 자동차가 있어서 카메라를 5초에 설치했다고 하자. 진출은 9초에 했다.
=> 그럼 다음과 같은 4가지 경우를 생각해 볼 수 있다.
3-1. 5초 이전에 진입 9초 이전에 진출 => 애초에 말이 안된다. 5초에 진입한 차가 가장 먼저 나간것이기 떄문(진출 기준 정렬)
3-2. 5초 이전에 진입 9초 이후에 진출 => 가능하다.
3-3. 5초 이후에 진입 9초 이전에 진출 => 이것도 말이 안된다. 3-1과 같은 이유
3-4. 5초 이후에 진입 9초 이후에 진출 => 가능하다.
=> 5초에 같이 진입하면 반드시 카메라에 찍히므로 배제할 수 있다.
=> 9초에 같이 진출하면 반드시 5초 이후에 진입해야 하므로 3-4의 경우로 볼 수 있다
4. 3-2와 3-4에 대해서 경우를 자세하게 따져보면,
=> 3-2는 5초에 있는 카메라에 반드시 찍힌다.
=> 3-4는 5초에 있는 카메라에 찍히지 못한다.
=> 이는 카메라의 위치보다 진입 시점이 더 뒤일 경우에 카메라가 더 필요하다는 것을 의미
5. 따라서, 카메라보다 진입시점이 늦은 자동차가 있을 경우 그 자동차의 진출시점으로 카메라를 추가
=> 왜 카메라를 진입시점이 아니라 진출시점으로 하는건데?
=> 이 자동차가 진입하고 진출할 때 까지 다른 자동차들을 추가로 더 찍을 수도 있으니까.
=> 진입시점으로 하면 매 차마다 카메라를 추가해야 하니까!
'''
def solution(routes):
    camera = -30001
    answer = 0
    routes.sort(key=lambda x: x[1])

    for route in routes:
        if camera < route[0]:
            answer += 1
            camera = route[1]

    return answer
'''
https://wwlee94.github.io/category/algorithm/greedy/speed-enforcement-camera/
아무리 생각해도 아이디어 구현이 잘 안돼서 위 링크 코드를 참조했다. (근데 코드가 너무 간단해서 아예 똑같음)
나는 우선순위 큐 쓰고 그랬는데 이렇게 간단한 코드라니...
'''