[프로그래머스][택배상자] Queue, stack만 사용해서 풀이

🤷‍♂️ 왜 블로그에 업로드?

어느 정도 알고리즘을 풀이하다보니 큐,스택을 사용해서 풀이를 해야겠다는 점이 보였다. 그러나 이 방법으로 풀이한 사람이 별로 없었고 난 어떻게든 큐, 스택을 사용해서 풀고 싶었다!

💡 자료구조 Hint

메인 컨베 -> 순차적으로 앞에서부터 나온다 -> FIFO
보조 컨베 -> 메인 컨베로부터 받은 게 안쪽에 들어가서 꺼낼꺼면 최근에 넣은 것부터 꺼내야한다 LIFO

🤔근데...

처음 풀이는 시간초과가 났다.
아무리 봐도 큐, 스택을 사용하는 것 같아서 납득이 안되서 찾아보다가 내 코드에서 contains를 통해서 어디 컨베이너에 들었나 확인하는 코드 때문에 시간 초과가 난 것이었다.

다른 사람들의 코드를 찾아보니 우선순위 큐, 스택만 사용한 경우 등 다양하게 풀이가 있었다.

---

🔍 큐,스택만 써서 풀이

contains로 인해서 시간 초과가 발생했다면 이 부분을 수정할 필요가 있었다.

어짜피 큐는 순차적으로 들어있다는 말이 있었으니까 1부터 n까지 정렬된 형식으로 들어있을 것이다.

그렇기 때문에 contains을 확인할 필요없이 메인 컨테이너 큐에 가장 먼저 나오는 값이 현재 찾는 값보다 작거나 같다는 조건을 이용해서 contains를 대신할 수 있다!

if(conve.size() > 0 && conve.peek() <= curBox){

아무튼 이런 경우라면 메인 컨테이너에 있으니 원하는 게 나올때까지 빼낸다!

만약 메인 컨테이너에 없다면 보조 컨테이너에 가장 최근 박스를 보고 일치하지 않는다면 break. 즉 더 이상 불가능한 진행으로 종료하면 된다!

---

🥽 코드

import java.util.*;

class Solution {
    public int solution(int[] order) {
        int answer = 0;
        Queue<Integer> conve = new LinkedList<>();
        Stack<Integer> helpConve = new Stack<>();
        
        for(int i=0;i<order.length;i++){
            conve.add(i+1);
        }
            
        for(int idx=0;idx<order.length;idx++){
            int curBox = order[idx];
            
            if(conve.size() > 0 && conve.peek() <= curBox){
                //있으면 당도할 때까지!
                while(conve.peek() != curBox){
                    helpConve.add(conve.poll());
                }
                conve.poll();
                answer++;
                continue;
            }
            
            //보조 컨베에 있니?
            if(helpConve.peek() == curBox){
                helpConve.pop();
                answer++;
            }
            else
                break;
        }
        return answer;
    }
}