택배상자

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

프로그래머스

 

문제의 설명에 따라, 메인 벨트는 Queue를, 서브 벨트는 Stack을, 서브로 옮겨졌는지 여부를 저장할 boolean[]을 사용했다.

 

 

원하는 박스가 서브 벨트로 옮겨졌는지 cache로 체크해보고, 서브 벨트에 없다면 메인 벨트에 있는 박스들을 서브벨트로 옮겨주는 방식..

 

 

import java.util.*;

class Solution {
    public int solution(int[] order) {
        Queue<Integer> main = new LinkedList();
        for (int i = 0; i < order.length; i++) {
            main.add(i + 1);
        }
        
        Stack<Integer> sub = new Stack();
        boolean[] cache = new boolean[order.length + 1];
        
        int answer = 0;
        int idx = 0;
        while (!main.isEmpty() || !sub.isEmpty()) {
            
            int need = order[idx];
            if (cache[need]) {
                int box = sub.pop();
                
                // 서브에 넣었던 박스인데, 서브 벨트의 마지막 박스가 아님. 멈춤
                if (box != need) break;
                
                answer++;
                idx++;
            } else {
                // 더이상 꺼낼 박스가 없음
                if (main.isEmpty()) break;
                
                int box = main.poll();
                if (box == need) {
                    answer++;
                    idx++;
                } else {
                    // 서브로 옮김
                    sub.push(box);
                    cache[box] = true;
                }
                
            }
            
        }
        
        return answer;
    }
}