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

문제 링크

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

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

풀이 

• 그리디 문제 

• def solution(routes):
    answer = 1
    # 나가는 시간 기준으로 오름차순 정렬
    routes.sort(key = lambda x : x[1])
    # 처음 카메라 위치는 가장 먼저 차량이 나간 지점 
    camera = routes[0][1]
  
    for i in range(1, len(routes)):
      # 만약 다음 차량이 출발한 시점보다 카메라가 전에 있으면 
      if camera < routes[i][0]:
      # 카메라 개수 하나 증가 
        answer += 1
      # 카메라 위치 다음 차량이 나간 지점으로 이동 
        camera = routes[i][1]
        
    return answer

• 예제 routes = [[-20,-15], [-14,-5], [-18,-13], [-5,-3]]의 경우 아래와 같다. 

- 반드시 진출 시점을 기준으로 정렬해야한다.

[[-100,100], [50,170], [150,200], [-50, -10], [10,20], [30,40]]]

의 답이 4인 것을 확인해보면 알 수 있다.