택배상자(Java)

bearMin·2024년 2월 15일

🎯문제

영재는 택배상자를 트럭에 싣는 일을 합니다. 영재가 실어야 하는 택배상자는 크기가 모두 같으며 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

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

✏️풀이

코드

import java.util.*;

class Solution {
    public int solution(int[] order) {
        int answer = 0;
        // 스택 생성
        Stack<Integer> stack = new Stack<>();
        
        // 1부터 N까지 반복
        for(int i = 1, j = 0; i <= order.length; i++) {
            // 스택에 값을 저장
            stack.add(i);
            // 스택이 비어있지 않으면서 스택의 맨 위 값이 순서와 맞을 때
            while(!stack.isEmpty() && stack.peek() == order[j]) {
            	// 값을 제거
                stack.pop();
                // answer 증가
                answer++;
                // order 순서 증가
                j++;
            }
        }
        
        return answer;
    }
}

설명

스택을 사용하여 문제를 해결하였다.

문제에서 가장 마지막에 보조 컨테이너 벨트에 보관한 상자부터 꺼내게 된다는 문장이 있었는데, 마지막에 들어온 것이 먼저 나가는 LIFO 구조는 스택이기 때문이다.

스택을 생성한 뒤 order 배열의 길이만큼 반복을 진행한다. order는 1 이상 order의 길이 이하 모든 정수가 한번씩 등장하며 순서대로 상자를 내릴 수 있다는 조건이 있다. 따라서 1부터 진행하여 order 배열의 길이보다 작거나 같을 때까지 반복을 진행하도록 하였다.

반복문을 시작하면서 스택에 값을 저장하였다. 이유는 스택에 넣어줘도 어차피 제일 먼저 확인을 할 수 있으며, 순서와 맞지 않다면 스택에 들어가야하기 때문이다.
그래서 스택에 값을 저장한 뒤에 스택이 비어있지 않으면서 스택의 맨 위 값을 확인했을 때 order 배열의 순서와 일치할 때까지 while문을 반복한다. while문에 들어가게 되면 일치하는 맨 위의 값을 제거하고, answer와 order의 순서를 증가시켜준다.

예를 들어,

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

일 때
[1, 2, 3, 4, 5]의 순서대로 반복문이 진행될 것이다. 그리고 스택에 값을 넣은 뒤에 해당 값이 order[0]과 동일 할 때까지 스택에 값을 넣는 것이다.
동일한 4가 스택에 들어가게 된다면, 4를 스택에서 제거하고 answer를 증가시킨 뒤 order의 순서를 하나 증가시켜 order[1]과 비교를 진행하게 된다. 이때 스택의 맨 위에 있는 값은 3이므로 역시 while문을 만족하게 되어 위의 과정을 동일하게 반복하게 된다.

위의 과정을 반복하면서 배열의 길이만큼 진행을 하고 반복문을 빠져나왔을 때 answer에 담겨있는 값이 구하려고 하는 값이 되고, answer를 반환하면 문제를 해결할 수 있다!