프로그래머스 - 택배상자(Java, 자바)

문제 링크

문제 설명

영재는 택배상자를 트럭에 싣는 일을 합니다. 영재가 실어야 하는 택배상자는 크기가 모두 같으며 1번 상자부터 n번 상자까지 번호가 증가하는 순서대로 컨테이너 벨트에 일렬로 놓여 영재에게 전달됩니다. 컨테이너 벨트는 한 방향으로만 진행이 가능해서 벨트에 놓인 순서대로(1번 상자부터) 상자를 내릴 수 있습니다. 하지만 컨테이너 벨트에 놓인 순서대로 택배상자를 내려 바로 트럭에 싣게 되면 택배 기사님이 배달하는 순서와 택배상자가 실려 있는 순서가 맞지 않아 배달에 차질이 생깁니다. 따라서 택배 기사님이 미리 알려준 순서에 맞게 영재가 택배상자를 실어야 합니다.

만약 컨테이너 벨트의 맨 앞에 놓인 상자가 현재 트럭에 실어야 하는 순서가 아니라면 그 상자를 트럭에 실을 순서가 될 때까지 잠시 다른 곳에 보관해야 합니다. 하지만 고객의 물건을 함부로 땅에 둘 수 없어 보조 컨테이너 벨트를 추가로 설치하였습니다. 보조 컨테이너 벨트는 앞 뒤로 이동이 가능하지만 입구 외에 다른 면이 막혀 있어서 맨 앞의 상자만 뺄 수 있습니다(즉, 가장 마지막에 보조 컨테이너 벨트에 보관한 상자부터 꺼내게 됩니다). 보조 컨테이너 벨트를 이용해도 기사님이 원하는 순서대로 상자를 싣지 못 한다면, 더 이상 상자를 싣지 않습니다.

예를 들어, 영재가 5개의 상자를 실어야 하며, 택배 기사님이 알려준 순서가 기존의 컨테이너 벨트에 네 번째, 세 번째, 첫 번째, 두 번째, 다섯 번째 놓인 택배상자 순서인 경우, 영재는 우선 첫 번째, 두 번째, 세 번째 상자를 보조 컨테이너 벨트에 보관합니다. 그 후 네 번째 상자를 트럭에 싣고 보조 컨테이너 벨트에서 세 번째 상자 빼서 트럭에싣습니다. 다음으로 첫 번째 상자를 실어야 하지만 보조 컨테이너 벨트에서는 두 번째 상자를, 기존의 컨테이너 벨트에는 다섯 번째 상자를 꺼낼 수 있기 때문에 더이상의 상자는 실을 수 없습니다. 따라서 트럭에는 2개의 상자만 실리게 됩니다.

택배 기사님이 원하는 상자 순서를 나타내는 정수 배열 order가 주어졌을 때, 영재가 몇 개의 상자를 실을 수 있는지 return 하는 solution 함수를 완성하세요.

---

제한사항

• 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

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 모든 상자를 보조 컨테이너 벨트에 모두 넣고, 역순으로 하나씩 빼서 트럭에 싣습니다.

---

문제 풀이 방법

컨테이너 벨트에 놓여 있는 택배는 큐의 특징으로 앞에 있는 물건이 먼저 나가게 된다.
보조 컨테이너 벨트는 가장 마지막에 놓인 택배가 가장 먼저 나가게 되는 스택의 특징을 가진다.
이 두개의 특징을 이용하여 큐와 스택을 이용해서 이 문제를 풀수 있다.

위와 같은 컨테이너벨트와 택배 순서가 주어져있다고 해보자.
메인 컨테이너벨트의 진행방향과 보조 컨테이너의 진행방향을 주의 깊게 봐야한다.

4 박스를 트럭에 실어야 한다.
하지만 메인 컨테이너벨트에는 4가 아닌 다른 숫자가 와있고, 보조 벨트에도 비어있거나 맞는 숫자가 없다.
4를 만날때까지 메인 컨테이너에서 보조 컨테이너벨트로 박스를 옮겨야한다.

4를 만나면 바로 컨테이너벨트에서 박스를 꺼내면 된다.

그다음 꺼내야할 박스는 3이다.
3번 박스는 보조 컨테이너벨트에 바로 첫번째에 있어 보조 컨테이너벨트에서 꺼내면 된다.

그다음 꺼내야 할 박스는 1이다.
1은 메인 컨테이너벨트에 없고, 보조 컨테이너벨트에 위치해있다.

하지만 보조 컨테이너벨트에서도 첫번째가 아닌 두번째에 위치해있다.

이것을 꺼내기 위해서는 보조 컨테이너벨트에서 맨앞에 있는 2번 박스를 꺼낸 다음 1을 꺼낼 수 있다.

하지만 보조 컨테이너벨트에서 임시로 둘 곳이 없으므로 1은 꺼내서 트럭에 실을 수 없게 된다.

if(!stack.isEmpty() && stack.peek() == cur){
    stack.pop();
    answer++;
}

이것을 코드로 보면 이 부분이 보조 컨테이너에 원하는 박스가 있는지 찾는 부분이다.
Null 방지를 위해서 isEmpty()를 사용하였고, 원하는 박스가 있으면 pop 으로 꺼낸 뒤 answer에 1을 더해 카운트 해주면 된다.

boolean flag = false;
while (!q.isEmpty()){
    if(q.peek() == cur){
        answer++;
        q.poll();
        flag = true;
        break;
    }
    else{
        stack.add(q.poll());
    }
}
if(!flag){
    break;
}

이 부분은 메인 컨테이너벨트 처리하는 곳이다.

메인 컨테이너벨트에서 원하는 값을 찾았는지 못찾았는지 확인하는 임시 변수로 flag 를 사용하였다.

만약 원하는 값을 찾았다면 큐에서 poll을 하고 flag 를 true 로 변환한다.

 

원하는 값을 찾지 못했다면 stack에 해당 값을 넣어 준다.

반복문을 나와서 flag 가 false 면 메인 컨테인벨트에 해당 값이 없다는 것이므로 더이상 트럭에 실을 수 없다는 뜻이 되므로 전체 반복문을 종료하면 된다.

---

전체 코드

import java.util.*;
class Solution {
    public int solution(int[] order) {
        int answer = 0;
        Queue<Integer> q = new LinkedList<>();
        Stack<Integer> stack = new Stack<>();

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

        for(int cur : order){
            if(!stack.isEmpty() && stack.peek() == cur){
                stack.pop();
                answer++;
            }
            else {
                boolean flag = false;
                while (!q.isEmpty()){
                    if(q.peek() == cur){
                        answer++;
                        q.poll();
                        flag = true;
                        break;
                    }
                    else{
                        stack.add(q.poll());
                    }
                }
                if(!flag){
                    break;
                }
            }
        }
        return answer;
    }
}