[알고리즘] 프로그래머스 - 단속카메라

프로그래머스 - 단속카메라

내 풀이

import sys

def solution(routes):
    answer = 0
    routes.sort(reverse=True)
    camera_pos = sys.maxsize
    for route in routes:
        if route[0] <= camera_pos <= route[1]:
            continue
        else:
            answer += 1
            camera_pos = route[0]
    return answer

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

처음에는 어떻게 접근해야할지 감이 안왔다. 그리디 문제라는 것을 몰랐으면 못풀었을 수도 있을 것 같다. 우선 routes를 reverse로 정렬해서 출발점이 가장 오른쪽에 있는 순서대로 정렬을 한다. 그리고 맨 처음 카메라는 sys.maxsize로 설정해놓는다. 그 다음은 routes를 반복문으로 돌면서 만약 현재 카메라 위치가 route의 범위에 있지 않다면 카메라를 추가하고, 카메라의 위치를 현재 route의 출발점으로 갱신하면된다.