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

링크 제목

https://school.programmers.co.kr/learn/courses/30/lessons/131704

 

풀이

1, 2, 3, ... n 순
컨베이어 벨트 일렬
1번부터 상자를 내릴 수 있음
    
미리 알려준 순서에 맞게
    
if (맨앞상자 != 트럭실어야한순): 
    보조 컨테이너 벨트에 보관
    맨앞 상자만 뺄 수 있음 
    (= 가장 마지막 보조컨테이너벨트에 보관한 상자부터 꺼내게 됨)
    if 보조컨베이어벨트이용 -> 원하는 순서X:
         더이상 싣지 않는다

 

order: 택배 기사님이 원하는 상자 순서를 나타내는 정수 배열

sbelt: 보조 컨테이너 벨트(sub container belt)에 있는 상자

cbelt: 컨테이너 벨트(container belt)에 있는 상자

truck: 트럭에 있는 상자

    
ex1)
초기상태

order = [4,3,1,2,5]
sbelt = [1,2,3,4,5]
cbelt = []
truck = []
    
order = [4,3,1,2,5]
sbelt = [2,3,4,5]
cbelt = [1]
truck = []
    
order = [4,3,1,2,5]
sbelt = [3,4,5]
cbelt = [2,1]
truck = []
    
order = [4,3,1,2,5]
sbelt = [4,5]
cbelt = [3,2,1]
truck = []
    
order = [3,1,2,5]
sbelt = [5]
cbelt = [3,2,1]
truck = [4]
    
order = [3,1,2,5]
sbelt = [5]
cbelt = [3,2,1]
truck = [4]
    
order = [1,2,5]
sbelt = [5]
cbelt = [2,1]
truck = [4,3]
    
ex2)
초기상태
order = [5,4,3,2,1]
sbelt = [1,2,3,4,5]
cbelt = []
truck = []
    
order = [5,4,3,2,1]
sbelt = [2,3,4,5]
cbelt = [1]
truck = []
    
order = [5,4,3,2,1]
sbelt = [3,4,5]
cbelt = [2,1]
truck = []

 

order = [5,4,3,2,1]
sbelt = [4,5]
cbelt = [3,2,1]
truck = []    

 

order = [5,4,3,2,1]
sbelt = [5]
cbelt = [4,3,2,1]
truck = []    

order = [4,3,2,1]
sbelt = []
cbelt = [4,3,2,1]
truck = [5]
    
order = [3,2,1]
sbelt = []
cbelt = [3,2,1]
truck = [5,4]
    
order = [2,1]
sbelt = []
cbelt = [2,1]
truck = [5,4,3]
    
order = [1]
sbelt = []
cbelt = [1]
truck = [5,4,3,2]
    
order = []
sbelt = []
cbelt = []
truck = [5,4,3,2,1]

 

이에 따라 다음과 같이 코드를 작성했다.

def solution(order):
    answer = 1
    
    l = len(order)
    sbelt = [i for i in range(1,l+1)]
    cbelt = []
    truck = []
    
    while len(order) > 0:       
        if len(sbelt) > 0 and sbelt[0] == order[0]:
            box = sbelt.pop(0)
            truck.append(box)
            order.pop(0)
        else:
            if len(cbelt) == 0:
                box = sbelt.pop(0)
                cbelt.insert(0, box)
            else:
                if cbelt[0] == order[0]:
                    box = cbelt.pop(0)
                    truck.append(box)
                    order.pop(0)
                else:
                    if len(sbelt) > 0:
                        box = sbelt.pop(0)
                        cbelt.insert(0, box)
                    else:
                        break
                                            
                
    answer = len(truck)
    
    return answer

하지만 시간초과가 되었다.

시간초과가 되지 않으려면 queue를 이용하면 된다.

다음 코드가 정답 코드이다.

전체 코드

from collections import deque

def solution(order):
    
    #위의 표현을 deque로 바꾸기
    l = len(order)
    order = deque(order)
    sbelt = deque([i for i in range(1,l+1)])
    cbelt = deque([])
    truck = deque([])
    
    while len(order) > 0:
        
        # print(order)
        # print(sbelt)
        # print(cbelt)
        # print(truck)
        # print()
        
        if len(sbelt) > 0 and sbelt[0] == order[0]:
            box = sbelt.popleft()
            truck.append(box)
            order.popleft()
        else:
            if len(cbelt) == 0:
                box = sbelt.popleft()
                cbelt.insert(0, box)
            else:
                if cbelt[0] == order[0]:
                    box = cbelt.popleft()
                    truck.append(box)
                    order.popleft()
                else:
                    if len(sbelt) > 0:
                        box = sbelt.popleft()
                        cbelt.appendleft(box)
                    else:
                        break
                                            
                
    answer = len(truck)
    
    return answer