택배 상자

from collections import deque

def solution(order):
    answer = 0
    mainStack, subStack = deque([i for i in range(1,len(order)+1)]), deque()

    for item in order:
    	# mainStack 존재
        if mainStack and mainStack[0] <= item:
            cur = mainStack.popleft()
            while cur != item:
                subStack.appendleft(cur)
                cur = mainStack.popleft()
            answer += 1
        else: # sub stack에 존재
            if subStack.popleft() == item:
                answer += 1
            else:
                break

    return answer

• Stack 형식을 deque로 구현함.

  무난한 구현이라고 생각했으나 테스트 케이스 4개에서 시간초과

첫번째 생각한 로직은 order 배열을 돌면서, mainStack에 item이 있는지 확인하는 if item in mainStack 이었는데, 이 탐색 부분에서 시간을 많이 잡아먹은 것 같았다.

order 배열에서 나중에 나올 원소들보다 큰 원소를 이미 처리 했으면, mainStack에는 그보다 작은 숫자는 없다는 점을 파악해서 오름차순 정렬되어 있는 mainStack의 첫 원소만을 비교하는 로직으로 바꿨더니 통과했다.

프로그래머스 연습문제, https://school.programmers.co.kr/learn/challenges