Programmers / 3단계 / 단속카메라 / python / 탐욕법(Greedy)

 

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

 

 

나의 풀이

def solution(routes):
    routes.sort(key = lambda x: x[1])
    camera = -30001
    cnt = 0
    
    for route in routes:
        if route[0] > camera:
            cnt += 1
            camera = route[1]
    
    return cnt

 1. 최소한의 카메라를 설치하기 위해 진출 지점을 기준으로 정렬한다.2. 제한사항을 고려해 camera를 -30001으로 놓는다.3. routes를 돌며 차량의 진입 지점이 카메라의 위치보다 크면 카메라의 수(cnt)를 증가시킨다.4. camera를 차량의 진출 지점으로 놓고 반복한다