[JS] 택배상자 - 구현 문제와 예외케이스

문제 요약

영재는 택배상자를 트럭에 싣는 일을 합니다. 영재가 실어야 하는 택배상자는 크기가 모두 같으며 1번 상자부터 n번 상자까지 번호가 증가하는 순서대로 컨테이너 벨트에 일렬로 놓여 영재에게 전달됩니다. 컨테이너 벨트는 한 방향으로만 진행이 가능해서 벨트에 놓인 순서대로(1번 상자부터) 상자를 내릴 수 있습니다. 하지만 컨테이너 벨트에 놓인 순서대로 택배상자를 내려 바로 트럭에 싣게 되면 택배 기사님이 배달하는 순서와 택배상자가 실려 있는 순서가 맞지 않아 배달에 차질이 생깁니다. 따라서 택배 기사님이 미리 알려준 순서에 맞게 영재가 택배상자를 실어야 합니다.

 

만약 컨테이너 벨트의 맨 앞에 놓인 상자가 현재 트럭에 실어야 하는 순서가 아니라면 그 상자를 트럭에 실을 순서가 될 때까지 잠시 다른 곳에 보관해야 합니다. 하지만 고객의 물건을 함부로 땅에 둘 수 없어 보조 컨테이너 벨트를 추가로 설치하였습니다. 보조 컨테이너 벨트는 앞 뒤로 이동이 가능하지만 입구 외에 다른 면이 막혀 있어서 맨 앞의 상자만 뺄 수 있습니다(즉, 가장 마지막에 보조 컨테이너 벨트에 보관한 상자부터 꺼내게 됩니다). 보조 컨테이너 벨트를 이용해도 기사님이 원하는 순서대로 상자를 싣지 못 한다면, 더 이상 상자를 싣지 않습니다.

 

예를 들어, 영재가 5개의 상자를 실어야 하며, 택배 기사님이 알려준 순서가 기존의 컨테이너 벨트에 네 번째, 세 번째, 첫 번째, 두 번째, 다섯 번째 놓인 택배상자 순서인 경우, 영재는 우선 첫 번째, 두 번째, 세 번째 상자를 보조 컨테이너 벨트에 보관합니다. 그 후 네 번째 상자를 트럭에 싣고 보조 컨테이너 벨트에서 세 번째 상자 빼서 트럭에싣습니다. 다음으로 첫 번째 상자를 실어야 하지만 보조 컨테이너 벨트에서는 두 번째 상자를, 기존의 컨테이너 벨트에는 다섯 번째 상자를 꺼낼 수 있기 때문에 더이상의 상자는 실을 수 없습니다. 따라서 트럭에는 2개의 상자만 실리게 됩니다.

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

 

제한사항

• 1 ≤ order의 길이 ≤ 1,000,000
• order는 1이상 order의 길이 이하의 모든 정수가 한번씩 등장합니다.
• order[i]는 기존의 컨테이너 벨트에 order[i]번째 상자를 i+1번째로 트럭에 실어야 함을 의미합니다.

 

테스트케이스

order	result
[4, 3, 1, 2, 5]	2
[5, 4, 3, 2, 1]	5

---

접근 방법

그냥 흐름대로 작성해주며 됩니다.

문제가 처음 읽으면 약간 난해한데, 박스가 1번부터 n번까지 상하차 식으로 몰려옵니다.

기사 아저씨가 이렇게 쌓아달라고 [4, 3, 1, 2, 5]로 보내면 그 순서대로 보조컨테이너를 이용해서 최대한 쌓아주면 됩니다.

 

테스트 케이스 1로 본 상태 값 관리

쌓아야할 박스: 4
이번 박스: 4
보조 컨테이너(stack): [1, 2, 3]
이미 실은 박스: []

 

쌓을 박스랑 이번 박스가 같으니 바로 실어주면 되겠네요.

쌓아야할 박스: 3
이번 박스: 5
보조 컨테이너(stack): [1, 2. 3]
이미 실은 박스: [4]

 

이번엔 다르지만, 보조박스에 넣어둔 3이 같기 때문에 그걸 넣어주면 되겠네요.

쌓아야할 박스: 1
이번 박스: 5
보조 컨테이너(stack): [1, 2]
이미 실은 박스: [4, 3]

 

둘 다 다르기 때문에 여기서 break해주면 됩니다.

약간의 예외처리와 stack에 남아있는 박스를 처리해주는 로직을 넣어주면 구현하는데 큰 어려움은 없습니다.

 

 

정답 코드

function solution(order) {
    const stack = [];
    const queue = new Queue();
    const n = order.length;
    let currOrder = 0;
    let box = 1;
    
    while (box <= n) {
        if (box === order[currOrder]) {
            queue.enqueue(box);
            currOrder++;
        } else {
            if (stack.length > 0) {
                const subContainerItem = stack.pop();
                if (subContainerItem === order[currOrder]) {
                    queue.enqueue(subContainerItem);
                    currOrder++;
                    box--;
                } else {
                    stack.push(subContainerItem);
                    stack.push(box);
                }
            } else {
                stack.push(box);
            }
        }
        box++;
    }
    
    while (stack.length > 0) {
        const val = stack.pop();
        if (order[currOrder++] === val) {
            queue.enqueue(val);
        } else break;
    }
    
    return queue.size();
}

class Queue {
    constructor() {
        this.queue = [];
        this.front = 0;
        this.rear = 0;
    }
    
    enqueue(val) {
        this.queue[this.rear++] = val;
    }
    
    dequeue() {
        const val = this.queue[this.front];
        delete this.queue[this.front++];
        return val;
    }
    
    isEmpty() {
        return this.front === this.rear;
    }
    
    size() {
        return this.rear - this.front;
    }
}

 

팁 1. 박스 비교 분기 설명

while (box <= n) {
    if (box === order[currOrder]) {
    // 이번 박스랑 쌓아야할 박스가 같은 경우
        queue.enqueue(box);
        currOrder++;
    } else {
        if (stack.length > 0) {
            const subContainerItem = stack.pop();
            if (subContainerItem === order[currOrder]) {
            // 보조 컨테이너에서 pop한 값이 같은 경우,
            // 이때는 box 커서를 움직이면 안됨.
                queue.enqueue(subContainerItem);
                currOrder++;
                box--;
            } else {
                stack.push(subContainerItem);
                stack.push(box);
            }
        } else {
            stack.push(box);
        }
    }
    box++;
}

 

테스트 1~5가 맞게 나오는데, 6~10이 틀리게 나오는 경우라면,

보조 컨테이너를 사용했을 때 다음 박스 커서를 움직이진 않았는지 확인해주세요.

저는 order: [1, 2, 4, 3, 5] 이 테스트 케이스로 잡아낼 수 있었습니다. 옳게 나오는 정답은 5에요.

 

팁 2. 마지막에 보조 컨테이너를 비워주기

while (stack.length > 0) {
    const val = stack.pop();
    if (order[currOrder++] === val) {
        queue.enqueue(val);
    } else break;
}

 

테스트케이스 2번의 경우, 1 ~ 4번 박스가 모두 보조 컨테이너로 들어가기 때문에,

남아있는 보조 컨테이너의 값을 비워줘야합니다.

 

---

 

코테 그래도 하루에 하나는 해야겠죠..?

너무 간만에 해서 머리가 굳었네요.