프로그래머스 택배상자(python)

from collections import deque

def solution(order):
    data = deque([i for i in range(1,len(order)+1)])
    sub_data = deque()
    answer = 0
    o = 0
    flag = 0
    s_flag = 0
    while True:
        if data:
            if order[o] > data[0]:
                sub_data.appendleft(data.popleft())
            elif order[o] == data[0]:
                data.popleft()
                answer +=1
                o += 1
            else:
                flag = 1
                pass
        else:
            if order[o] == sub_data[0]:
                answer += 1
                sub_data.popleft()
                o += 1
                if o > len(order)-1:
                    break
            else:
                break
        if flag == 1:
            if order[o] == sub_data[0]:
                answer += 1
                sub_data.popleft()
                o += 1
            else:
                 s_flag = 1
        if flag ==1 and s_flag == 1:
            break
        if flag ==1:
            flag = 0
    return answer

처음에 문제에서 예제 1번을 설명을 해주는데 이해가 안 돼서 문제 이해하는 데에만 30분가량을 쏟았다.

 

order가 [4,3,1,2,5]일 때 본 컨테이너 벨트에는 [1,2,3,4,5]가 있고 이것과 부 컨테이너 벨트 하나를 더 이용하여 order 모양으로 만드는 것이다. 처음에는 stack으로 풀어볼까 했지만 stack으로 풀면 top 인덱스를 따라다닐 변수를 두 개 더 만들어야 해서 queue로 풀었다.

 

일단 여기에는 똑같은 두개 이상의 정수가 없다는 점과 본 컨테이너 벨트에는 크기 순서대로 있다는 것을 인지해야 한다.

 

무한 반복을 돌면서 기사님이 싣고 싶어하는 상자의 번호와 같을 때까지 부 벨트에다가 넣어줘야 한다.  같아졌다면 본 컨테이너 벨트에서 상자를 내려주고 결값과 order 인덱스 값을 1씩 올려준다.  그리고 order값이 data의 있는 값보다 작다면 flag =1을 넣어준다. else를 넣어준 이유는 data의 값이 없어질 수 있기 때문이다.

 

 그 다음 깃발에 1이 들어가 있을 때 부 컨테이너 벨트로 넘어갈 것이다. 부 컨테이너 벨트의 입구에 있는 값과 기사님이 원하는 값이 같은지를 비교한다. 다르다면 s_flag 에다가 1을 넣어준다. 그러고 flag도 1 s_flag도 1이라면 while을 탈출한다.

 

※ 반례도 많을 것이라고 생각했고 문제 조건에서 order의 길이가 최대 백만이라 하여 시간 초과가 날 것 같았는데 맞았다. 문제를 풀었지만 왜 맞았는지 모르겠다 왜 맞았는지 아시는 분은 알려주시면 감사하겠습니다 (_ _)