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

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

프로그래머스

 

풀이

 

보조 컨테이너 벨트는 앞 뒤로 이동이 가능하지만 입구 외에 다른 면이 막혀 있어서 맨 앞의 상자만 뺄 수 있습니다(즉, 가장 마지막에 보조 컨테이너 벨트에 보관한 상자부터 꺼내게 됩니다).
위 문장에서 말하는 "보조 컨테이너 벨트에 보관한 상자"를 생각해보면,
보조 컨테이너 벨트는 상자들을 쌓는 구조로 이루어져 있을 것이다.
그렇다면  stack 자료구조를 사용하는것이 적절하다.

먼저 seq는 상자들의 배열을 옮겨담은 변수이고,
stack은 보조 컨테이너 벨트를 나타낸다.
idx는 상자의 번호를 의미한다(담아야 하는 상자는 1부터 N까지 있다.)

그 후 다음 과정을 반복한다.
1. 보조 컨테이너 벨트와 현재 넣어야 할 상자의 값이 일치하는지 확인한다. 만약 일치한다면 상자를 제거
2. 현재 상자의 번호와 넣어야 할 상자의 값이 일치하는지 확인한다. 
   -> 일치하면 ? seq에서 상자 제거
   -> 일치하지 않으면 ?  해당 상자를 보조 컨테이너 벨트에 추가
3. 상자의 번호가 N을 초과하면 반복 종료

최종적으로 seq에 남아있는 것들은 제거되지 못한 상자들이므로,
"총 상자의 개수 - 제거되지 못한 상자의 개수"를 리턴하면 된다.

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
import java.util.Stack;

class Solution {

    public int solution(int[] order) {

        Queue<Integer> seq = new LinkedList<>();
        Stack<Integer> stack = new Stack<>();

        for (Integer integer : order) seq.add(integer);

        int idx = 1;

        /**
         * 1. seq에는 추출해야하는 순서가 들어있음
         * 2. stack에서 seq와 일치하면 둘 다 하나씩 빼주며 반복
         * 3. idx와 seq가 일치하면 seq에서 제거
         */

        while (true) {

            while (!stack.isEmpty() && Objects.equals(stack.peek(), seq.peek())) {
                seq.poll();
                stack.pop();
            }

            if (!seq.isEmpty() && seq.peek() == idx) seq.poll();
            else stack.add(idx);

            if (idx++ > order.length) break;
        }

        return order.length - seq.size();
    }
}