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

❓문제

프로그래머스

성능 요약

반복문 ➡️ 메모리: 132 MB, 시간: 189.21 ms

큐 ➡️ 메모리: 190 MB, 시간: 191.63 ms

문제 설명

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

컨테이너 벨트는 한 방향으로만 진행이 가능해서 벨트에 놓인 순서대로(1번 상자부터) 상자를 내릴 수 있습니다.

택배 기사님이 미리 알려준 순서에 맞게 택배상자를 실어야 합니다.

만약 컨테이너 벨트의 맨 앞에 놓인 상자가 현재 트럭에 실어야 하는 순서가 아니라면 그 상자를 트럭에 실을 순서가 될 때까지 잠시 보조 컨테이너 벨트에 보관해야 합니다.

보조 컨테이너 맨 앞의 상자만 뺄 수 있습니다(즉, 가장 마지막에 보조 컨테이너 벨트에 보관한 상자부터 꺼내게 됩니다).

보조 컨테이너 벨트를 이용해도 기사님이 원하는 순서대로 상자를 싣지 못 한다면, 더 이상 상자를 싣지 않습니다.

---

제한사항

• 1 ≤ order의 길이 ≤ 1,000,000
• order는 1이상 order의 길이 이하의 모든 정수가 한번씩 등장합니다.
• order[i]는 기존의 컨테이너 벨트에 order[i]번째 상자를 i+1번째로 트럭에 실어야 함을 의미합니다.

---

입출력 예

order	result
[4, 3, 1, 2, 5]	2
[5, 4, 3, 2, 1]	5

✍🏻풀이

택배 기사님이 원하는 순서로 택배 상자를 차에 싣을 때,
기존 컨테이너 벨트(반복문 or 큐)와 순서가 맞지 않는다면 보조 컨테이너 벨트(스택)에 넣는다.
이후 보조 컨테이터 벨트의 맨 앞의 상자가 원하는 순서라면 이를 꺼낸다.
원하는 순서와 맞을 때마다 answer + 1을 한다.

💻코드

/** 스택과 큐 이용한 풀이 **/
import java.util.*;

class Solution {
    public int solution(int[] order) {
        int answer = 0;
        Stack<Integer> s = new Stack<>();
        Queue<Integer> q = new LinkedList<>();

        for(int i = 1; i <= order.length; i++){
            q.add(i);
        }

        int i = 0;
        while(!q.isEmpty()){
            int o = q.poll();
            if(o != order[i]){
                s.push(o);
            }
            else {
                i++;
                answer++;
                while(!s.isEmpty() && s.peek() == order[i]){
                    s.pop();
                    answer++;
                    i++;
                }
            }
        }

        return answer;
    }
}

 

/** 반복문과 스택을 이용한 풀이 **/
import java.util.*;

class Solution {
    public int solution(int[] order) {
        int answer = 0;
        Stack<Integer> s = new Stack<>();
        int idx = 0;
        for(int i = 1; i <= order.length; i++){
            s.add(i);
            while(!s.isEmpty() && s.peek() == order[idx]){
                s.pop();
                answer++;
                idx++;
            }
        }

        return answer;
    }
}