[프로그래머스/Lv.2] 택배상자 (Java)

택배상자

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

---

풀이

• `Deque<Integer> sub = new ArrayDeque<>()`: 보조 컨테이너
• `idx`: 다음에 반드시 실어야 하는 `order` 위치
• `box`: 컨베이어에서 다음에 나올 번호

 

컨베이어 벨트에서 꺼낼 상자가 남아 있는 동안 

• 보조 컨테이너 X
  • `order[idx] == box`: 컨테이너 벨트의 맨 앞에 놓인 상자가 현재 트럭에 실어야 하는 순서
• 보조 컨테이너 O
  • 지금 상자 X + 현재 스택 top O => 지금 안꺼내면 다음에 X -> 바로 꺼내기
  • 지금 상자 X + 현재 스택 top X => 보관 (일단 저장)

while (box <= n) {
    if (order[idx] == box) {
        idx++;
        box++;
    } else if (!sub.isEmpty() && sub.peek() == order[idx]) {
        sub.pop();
        idx++;
    } else {
        sub.push(box);
        box++;
    }
}

 

• `!sub.isEmpty()`: 컨베이어 벨트 X But, 보조 컨테이너(`sub`)에 상자 쌓여 있음
• `idx < n`: 아직 실어야 할 `order` 남아 있음
• `sub.peek() == order[idx]`: `sub` 맨 위 상자만 꺼낼 수 있고 그 상자가 지금 필요한 `order[idx]`

while (!sub.isEmpty() && idx < n && sub.peek() == order[idx]) {
    sub.pop();
    idx++;
}

---

코드

import java.util.*;

class Solution {
    public int solution(int[] order) {
        Deque<Integer> sub = new ArrayDeque<>();
        int idx = 0;
        int box = 0;
        int n = order.length;
        
        while (box <= n) {
            if (order[idx] == box) {
                idx++;
                box++;
            } else if (!sub.isEmpty() && sub.peek() == order[idx]) {
                sub.pop();
                idx++;
            } else {
                sub.push(box);
                box++;
            }
        }
        
        while (!sub.isEmpty() && idx < n && sub.peek() == order[idx]) {
            sub.pop();
            idx++;
        }
        
        return idx;
    }
}