프로그래머스: 단속 카메라 (python)

from collections import deque
def solution(routes):
    answer = 0
    # 먼저 빠져나가는 순서대로 정렬
    routes.sort(key=lambda a : a[1])
    # 만약 route[i][1] 번째 있는 것을 고른다
    rqueue = deque(routes)
    while rqueue:
        x, y = rqueue.popleft()
        answer +=1
        if not rqueue:
            break
        while rqueue:
            if rqueue[0][0]<=y<=rqueue[0][1]:
                rqueue.popleft()
            else:
                break
    return answer

 

그리디 알고리즘으로 푸는 문제입니다.

 

1. 먼저 자동차가 빠져나가는 순서대로 정렬을 해주도록합니다. 

그러면 routes[x][1]을 보고서 정렬을 해주면 됩니다.

2. deque로 만들어주도록 합니다.

3. x,y = popleft()를 해줄 때마다 카메라가 하나씩 증가합니다.

4. 만약 y값이 그 다음값에 route경로에 사이값에 있다면 popleft해주도록 합니다.

5. 없다면 break

 

그리디로 푼다는 것을 생각만 잘하면 어렵지 않게 풀 수 있었습니다.