프로그래머스 Lv2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 25분

from collections import deque

def solution(order):
    answer = 0
    length =len(order)
    order = deque(order)
    con1 = deque([i for i in range(1,length+1)]) # queue
    con2 = [] # stack
    
    while order:

        find  = False
        x = order.popleft()
        
        if con2 and con2[-1]==x:
            con2.pop()
            answer += 1
            continue
        
        while con1:
            b1 = con1.popleft() 
            if b1==x:
                answer+=1
                find = True
                break
            else:
                con2.append(b1)
        
        if not find:
            break
        
    return answer

1번~n번까지 순서대로 택배 상자를 받을 수 있고 택배 기사님이 미리 알려준 순서(order)대로 트럭에 실어야 하는 문제입니다.🐤🐤🐤

단, 순차적으로 택배 상자를 받는 컨베이어 벨트의 상자가 현재 실어야 하는 순서(order)에 맞지 않을 때는 보조 컨베이어에 벨트에 임시 보관할 수 있습니다. 이때 보조 컨베이어 벨트는 마지막에 넣은 상자를 먼저 꺼낼 수 있는 조건입니다.

문제를 이해하고 Queue, Stack 구조를 활용하여 풀어내고자 하였습니다.

택배 기사님이 알려주신 순서(order)를 돌며 목표한 상자(x)를 정의하고
먼저 보조 컨베이어 벨트에 마지막 상자(con2.pop())가 목표한 상자(x)가 맞는지 확인합니다.

이가 아니라면, 본 컨베이어벨트에서(con1) 순차적으로 목표한 상자(x)가 나올때까지 확인합니다. 본 컨베이어 벨트(con1)에서 목표한 상자(x)를 찾을 때까지 보조 컨베이어 벨트(con2)에 추가하며 만약 모든 과정에서 찾지 못한다면 break하여 현재까지 순서가 맞은 상자만큼 return 하게 됩니다.

[다른 사람의 풀이1]

def solution(order):
    answer = 0
    stacks = []
    N = len(order)
    i = 1
    idx = 0
    while i < N+1:
        stacks.append(i)
        while stacks[-1] == order[idx]:
            idx += 1
            stacks.pop()
            if len(stacks) == 0:
                break
        i += 1

    return idx

본 컨베이어 벨트에서 순차적으로 받은 택배 상자를 바로 보조 컨베이어 벨트에 넣은 뒤 확인하는 방식이 나의 풀이'와 달랐습니다.🐱🐱🐱

[다른 사람의 풀이2]

from collections import deque  
def solution(order):  
    
    answer = 1  
    order = deque(order)  
    stack = []  
    result = []  
    size = len(order)

    for i in range(1, size + 1):  
        stack.append(i)  #박스를 서브 컨테이너에 옮긴다
        while stack:  
            if order and stack[-1] == order[0]:  #서브 컨테이너에서 트럭으로 옮긴다
                num = stack.pop()  
                order.popleft()  
                result.append(num)  
            else:  #만약 트럭으로 옮기는 순서가 잘못 됐다면 중지한다.
                break 

    return len(result) #트럭에 실은 박스 갯수를 반환한다.

'다른 사람의 풀이1'처럼 본 컨베이어 벨트에서 순차적으로 받은 택배를 조건문없이 바로 보조 컨베이어 벨트에 넣고, 보조 컨베이어 벨트의 마지막 택배 상자를 확인하는 순서로 구현한 방식입니다.🐕🐕🐕

감사합니다.