프로그래머스 - 택배상자 (파이썬)

스택과 큐 사용

 

def solution(order):
    answer = 0
    i_order=0 #현재 orderd의 인덱스
    i_que=0 #큐의 앞에 값을 하나씩 없애면 시간복잡도 O(n)이기 때문에 값 없애지 않고 인덱스 증가시킴
    que=[]
    stack=[]
    for i in range(1,len(order)+1):
        que.append(i)

    while i_order<len(order): 
        if i_que<len(que) and que[i_que]==order[i_order]:  #큐의 첫번째 값과 order의 해당 인덱스의 값의 동일할때
            i_order+=1 #order의 인덱스 증가
            i_que+=1 #que의 인덱스 증가
            answer+=1
        else:
            if len(stack) and stack[-1]==order[i_order]: #스택에 값이 있고 스택의 맨 위의 값과 order의 해당 인덱스의 값이 동일할때 
                stack.pop() #스택의 맨 위의 값 삭제
                i_order+=1 #order의 인덱스 증가
                answer+=1
            elif i_que<len(que):
                stack.append(que[i_que]) #que에서 stack으로 옮길 값 존재하면 옮김
                i_que+=1 
            else: #큐에서 스택으로 옮길 값도 없고 스택에서 pop도 일어나지 않는다면 더이상 옮길 수 있는 택배 존재하지 않음
                break
    
    return answer