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

[유형]

그리디 

 

[문제링크]

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

 

[요약]

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

 

[문제풀이]

도착지점을 기준으로 정렬을 한다.

첫번째 도착지점에 단속카메라를 설치(prev_end)하고, 다음 차량의 출발지점(start)이 도착지점(prev_end)보다 크면 새로운 단속카메라를 설치한다.

def solution(routes):
    answer = 1
    routes.sort(key= lambda x: x[1])
    prev_end = routes[0][1]
    
    for start,end in routes:
        if start > prev_end:
            answer +=1
            prev_end = end
    
    return answer