[프로그래머스][JAVA]Lv. 2 - 택배상자 문제

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

프로그래머스

1 ~ order.length의 상자를 order[]에 맞게 트럭에 싣는 문제이다.

트럭에 순서에 맞게 실어야 하지만, 그러지 못할 때는 보조 컨테이너 벨트에 싣고 거기에서 빼서 트럭에 실을 수 있다.

트럭은 ArrayList, 보조 컨테이너 벨트는 한쪽 입구로만 뺄 수 있는 규칙이 있기에 Stack으로 설정하고 문제를 풀었다.

import java.util.ArrayList;
import java.util.Stack;
class Solution {
    public int solution(int[] order) {
        Stack<Integer> st = new Stack<>();
        ArrayList<Integer> al = new ArrayList<>();
        int n = 0;
        for (int i = 0; i < order.length; i++) {
            if (i + 1 != order[n]) {
                st.push(i+1);
            } else {
                al.add(i+1);
                n++;
            }
            if (!st.isEmpty() && !al.isEmpty() && st.peek() == order[n]) {
                al.add(st.pop());
                n++;
            }
        }
        while (!st.isEmpty()) {
            if (order[n] == st.peek()) {
                al.add(st.pop());
                n++;
            } else {
                break;
            }
        }
        return al.size();
    }
}

먼저 위쪽 for 문으로 트럭에 싣거나 보조 컨테이너 벨트에 싣고, 보조 컨테이너 벨트에서 뺄 수 있는 것이 순서에 맞는 것이라면 트럭에 싣는다.

while 문에서는 st (보조 컨테이너 벨트)를 peek 했을 때, 그 값이 순서에 맞는다면 al (트럭)에 싣고

순서에 안 맞는 경우에는 더 이상 진행이 불가능하기에 break으로 while 문을 빠져나오게 했다.

 

첫 번째 예시 [4, 3, 1, 2, 5]의 경우

st = [1] [1, 2] [1, 2, 3] [1, 2] [1, 2, 5] (보조 컨테이너 벨트)
al =  []     []         []      [4, 3]  [4, 3] (트럭)

그리고 더 이상 while 문을 통해서 트럭에 실을 수 없기 때문에 2개가 실리게 된다.

 

두 번째 예시 [5, 4, 3, 2, 1]의 경우

st = [1, 2, 3]

al = [5, 4]가 되고, 이후 while 문에서 반복하여 트럭에 실어서

al = [5, 4, 3, 2, 1] 이 된다.