[프로그래머스] 택배상자

문제 출처: 프로그래머스

프로그래머스

 

문제 설명

🔎 한 방향으로만 진행하는 컨테이너 벨트에 놓인 순서대로 번호가 있는 택배 상자를 순차적으로 꺼내서 택배 기사님에게 전달합니다.
택배는 반드시 1, 2, 3, ..., n 순서대로 꺼내서 전달해야하며, 만약 꺼내야할 상자가 뒤에 있다면 앞에 있는 택배 상자들은 꺼내서 임시 컨테이너 벨트에 넣습니다. 임시 컨테이너 벨트에서 꺼내는 동작 또한 순차적으로 진행되어야 합니다. 만약 양 컨테이너 벨트에서 원하는 물건을 꺼낼 수 없는 경우 더 이상 상자를 전달하지 않습니다.

5개의 상자가 있고, 택배 기사님이 원하는 순서가 [4, 5, 1, 2, 3] 이라면
원래 컨테이너 벨트에서 [1, 2, 3]을 빼내서 임시 컨테이너 벨트에 [3, 2, 1] 순서로 놓고, 4를 택배 기사님께 전달합니다. 이후 [5]를 원래 컨테이너 벨트에서 빼 전달합니다.
[1]은 원래 컨테이너 벨트에서도, 임시 컨테이너 벨트에서도 바로 얻을 수 없으므로 더 이상 상자를 전달하지 않습니다.

택배 기사님이 원하는 상자 순서를 나타내는 정수 배열 order가 주어졌을 때, 몇 개의 상자를 실을 수 있는지 return 하는 solution 함수를 완성하세요.

예제 설명

처음 문제를 읽었을 때 너무 길고 이해하는데 오래 걸려서 이해한 맥락으로 문제를 요약하였다.

 

문제는 길었으나 간단히 보면 queue를 이용해서 문제를 풀라는 말이었다.

 

<정답 코드>

from collections import deque
def solution(order):
    answer = 0
    q = deque([i+1 for i in range(len(order))])
    temp = deque()
    
    for i in order:
        if q and q[0] <= i:
            while q[0] != i:
                temp.appendleft(q.popleft())
            q.popleft()
            answer += 1
        
        else:
            if i == temp[0]:
                temp.popleft()
                answer += 1
            else:
                return answer
        

    return answer

접근은 아래와 같다.

1. 두 개의 컨테이너 벨트를 deque로 구현한다. 기존 컨테이너 벨트는 순서대로 채운다.
2. 상자를 전달하기 위해서는 아래 두가지 조건에 만족되어야 한다.
   1. 기존 컨테이너 벨트에 그 상자가 존재할 경우 그 상자 앞의 모든 상자를 임시 컨테이너 벨트로 옮긴 후 전달한다.
   2. 상자가 임시 컨테이너 벨트에 존재한다면, 그 상자가 맨 앞에 있을 경우에만 전달 가능하다.

위 조건을 만족하지 않으면 바로 탈출하게 끔 코드를 작성하였다.

 

프로그래머스로 문제를 접하면 엄청난 길이의 문제 설명으로 당황할 수 있지만, 핵심만 파악한다면 쉽게 풀 수 있는 문제라고 생각한다.