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

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

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

 

정렬을 통하여 차례대로 카메라를 반드시 설치하여야 하는 경우를 세어준다.

 

[-20, 15] 만을 본다면 적어도 15 이하에는 카메라가 설치되어 있어야 한다.

 

다음 순서인 [-14, -5] 를 봤을 때는 -14 가 -20 보다 크다는 것은 sort() 로 보장되어 있다. 즉, 15 가 -14 보다 크다면

15 와 [-14, -5] 에서 나간 지점은 5 랑 비교하여 작은 값에 카메라를 설치하는 것이 이상적이다. 반대로 작다면, 카메라 1대로 두 구간을 확인하는 것이 불가능하므로 answer 에 1을 더하여준다.

 

def solution(routes):
    answer = 1
    routes.sort()
    camera = routes[0][1]
    
    for i in range(1, len(routes)):
        if routes[i][0] <= camera:
            camera = min(camera, routes[i][1])
        else:
            answer += 1
            camera = routes[i][1]
            
    return answer

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