(Python/LV3) 단속카메라

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/42884

프로그래머스

풀이:

def solution(routes):
    routes.sort(key = lambda x:x[1])
    camera = routes[0][1]
    res = 1
    for i in range(1, len(routes)):
        if camera < routes[i][0]:
            camera = routes[i][1]
            res +=1
    return res

 

차가 나가는 기준 으로 정렬을해준다.

routes.sort(key = lambda x:x[1])


print(solution([[-20,-15], [-14,-5], [-18,-13], [-5,-3]]))
>>
[[-20, -15], [-18, -13], [-14, -5], [-5, -3]]

 

camera = routes[0][1]
res = 1

제일 첫 카메라는 첫번째 차량이 나가는 곳 (최대값)에 설치를 해준다 [-15] res 카메라갯수 1개

 

for i in range(1, len(routes)):
    if camera < routes[i][0]:
        camera = routes[i][1]
        res +=1
return res

포문을 돌면서

만약에 카메라 설치한곳이 그 다음 출입시간보다 크면 카메라를 설치할필요가없다

ex) [-20,-15] 에 카메라는 -15에 설치가 되어있고

[-18,-13] 과 비교하면 -15에 있는 카메라에 찍히니깐 카메라가 필요없다

 

그래서 출입시간이 카메라설치한곳보다 작으면 카메라를 하나 설치해주고 res+=1

camera를 바뀐 차량이 나가는 곳 (최댓값) 으로 바꿔준다