[Programmers] 단속카메라
고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.
routes | return |
---|---|
[[-20,-15], [-14,-5], [-18,-13], [-5,-3]] | 2 |
-5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.
-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.
routes
)를 마지막 지점을 기준으로 정렬한다.std
)이 차량 경로의 시작 지점(s
)보다 짧다면 단속 카메라(std
)의 위치를 차량 경로의 끝지점(e
)으로 갱신하고 카메라의 개수(answer
)를 1
증가시킨다.✍ 코드
def solution(routes):
answer = 0
routes.sort(key = lambda x : x[1])
std = -30001
for s, e in routes:
if std < s:
std = e
answer += 1
return answer