[코테] 큐와 스택 - 택배상자[프로그래머스]

문제

출처: 프로그래머스 - 택배상자

풀이

1번부터 증가하는 상자가 컨테이너에서 순서대로 흘러올 때, 'order'의 번호와 같을 때 트럭에 실으면 된다.
순서가 같지 않으면 임시 컨테이너에 집어넣는데, 그 컨테이너는 스택과 같이 후입선출만 가능하다.
그래서 일단 임시 컨테이너에 집어넣고, 제일 마지막에 집어넣은 컨테이너의 번호와 'order'의 번호가 같은면 트럭에 실어야 하기에 answer을 1씩 올려준다.
트럭에 실은 택배 번호는 삭제시켜야 하기에 order은 큐 자료구조로 임시 컨테이너는 stack로 변수를 설정한다. 'order'의 길이는 백만이기에 큐 자료구조로 하지 않으면 O(n**2)이 되어 시간초과가 될 수 있다.

코드

from collections import deque
def solution(order):
    order = deque(order)
    n = len(order)
    answer = 0
    tmp = [] # 임시 컨테이너

    for i in range(1, n+1): # 번호 1번 상자부터 시작한다.
        tmp.append(i) # 임시 컨테이너에 집어넣는다.
        while tmp and tmp[-1] == order[0]:
            answer += 1
            order.popleft()
            tmp.pop()

    return answer