프로그래머스 단속카메라 파이썬**

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

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

 

이 문제의 가장 탐욕스러운 방법은 진출지점 기준으로 오름차순으로 정렬한 후, 진출지점에 카메라를 설치하는 것이다.

 

왜냐하면 진출지점이 오름차순 정렬돼있기 때문에 첫번째 진출지점에 카메라를 설치하면 다음 자동차는 무조건 첫번째 진출지점 이후에 진출하기 때문에 카메라를 만나기에 가장 최선이다.

 

풀이:

1. 진출지점 기준으로 오름차순 정렬한다.

 

2. 자동차를 순회한다.

 

3. 만약 카메라가 현재 자동차의 시작지점 이전에 있다면 그 차는 카메라를 만나지 못한 것이므로 카메라를 설치한다.

-> 만약 카메라가 시작지점 이후에 있다면 무조건 단속된다.

왜냐하면 카메라가 설치된 위치는 진출지점이고 진출지점은 기준으로 오름차순 정렬돼있기 때문에 이전에 설치된 카메라는 이후에 설치된 카메라보다 진출지점이 무조건 이전이다. 그러므로 카메라가 설치된 위치가 진입지점보다 이후라면 무조건 단속된단.

 

 

def solution(routes):
    answer = 0
    routes.sort(key=lambda x: x[1])
    camera = -30001
    print(routes)
    for i in range(len(routes)):
        en, ex = routes[i]
        if camera < en:
            answer += 1
            camera = ex

    return answer


print(solution([[15, 20], [5, 14], [13, 18], [3, 5]]))
# routes	                                    return
# [[-20,-15], [-14,-5], [-18,-13], [-5,-3]]	    2