[프로그래머스] Lv.2 : 택배상자 - 자바[Java]

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

프로그래머스

 

풀이

영재가 실어야 하는 택배상자는 크기가 모두 같으며 1번 상자부터 n번 상자까지 번호가 증가하는 순서대로 컨테이너 벨트에 일렬로 놓여 영재에게 전달됩니다.

-> 주 컨테이너는 1번부터 n번까지 순서대로 전달되므로 큐 자료구조를 사용한다.

 

보조 컨테이너 벨트는 앞 뒤로 이동이 가능하지만 입구 외에 다른 면이 막혀 있어서 맨 앞의 상자만 뺄 수 있습니다(즉, 가장 마지막에 보조 컨테이너 벨트에 보관한 상자부터 꺼내게 됩니다).

-> 보조 컨테이너는 스택 자료구조를 사용한다.

 

로직

1. 큐와 스택을 생성한다.

2. 큐에 1~n까지 삽입한다.

3. 각 상자 순서마다 다음을 수행한다.

- 큐가 비어있거나 큐 맨앞에 있는 상자가 현재 순서의 상자보다 큰 숫자일 경우, 스택에서 상자를 꺼내야 한다.

스택이 비어있거나 스택 맨 앞에 있는 상자가 현재 순서의 상자와 다르면 break하고, 스택 맨 앞에 있는 상자가 현재 순서의 상자와 같다면 스택에서 꺼낸 후 cnt++

- 큐 맨앞에 있는 상자가 현재 순서의 상자와 같다면, 큐에서 꺼내고 cnt++

- 큐 맨앞에 있는 상자가 현재 순서의 상자보다 작다면, 현재 순서의 상자 전까지 큐에 있는 상자들을 차례대로 스택에 넣고 큐에서 꺼낸다음 cnt++

코드

import java.util.*;

class Solution {
    public int solution(int[] order) {
        int n = order.length;
        Queue<Integer> q = new ArrayDeque<>();
        Stack<Integer> st = new Stack<>();
        
        // 1~n까지 큐에 삽입
        for (int i = 1; i <= n; i++) {
            q.add(i);
        }
        
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            int box = order[i];
            
            if (q.isEmpty() || q.peek() > box) {
                // 스택에서 상자 꺼내기
                if (st.isEmpty() || st.peek() != box) break;
                
                if (st.peek() == box) {
                    st.pop();
                    cnt++;
                }
            }
            else if (q.peek() == box) {
                q.poll();
                cnt++;
            }
            else if (q.peek() < box) {
                // 큐에 있는 상자들을 차례대로 스택에 넣어야 함
                while (q.peek() < box) {
                    st.push(q.poll());
                }
                q.poll();
                cnt++;
            }
        }
        return cnt;
    }
}

 

다른 풀이

import java.util.*;
class Solution {
    public int solution(int[] order) {
        int idx = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < order.length; i++){
            stack.push(i+1);
            while(!stack.isEmpty()){
                if (stack.peek() == order[idx]){
                    stack.pop();
                    idx++;
                } else break;
            }
        }

        return idx;
    }
}