[프로그래머스/Java] 택배상자

문제 설명

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

프로그래머스

영재는 택배상자를 트럭에 싣는 일을 합니다. 영재가 실어야 하는 택배상자는 크기가 모두 같으며 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;
        // order의 길이
        int len = order.length;
        // order의 인덱스 위치
        int orders = 0;
        
        // 보조 컨베이어 역할의 스택 생성
        Stack<Integer> stack = new Stack<>();
        
        // 반복문을 통해 상자 적재
        for (int i = 1; i <= len; i++) {
            // 바로 적재할 수 있으면
            if(orders < len && i == order[orders]) {
                answer++;
                orders++;
            // 일단 보조 컨베이어에 적재
            } else {
                stack.push(i);
            }
            
            // 스택에서 연속으로 꺼낼 수 있을 때까지 꺼내기
            while (orders < len && !stack.isEmpty() && stack.peek() == order[orders]) {
                stack.pop();
                answer++;
                orders++;
            }
        }
        
        // 남은 스택 처리 (for 끝난 뒤에도 더 적재할 수 있으면 계속 진행)
        while (orders < len && !stack.isEmpty() && stack.peek() == order[orders]) {
            stack.pop();
            answer++;
            orders++;
        }
        
        // 정답 반환
        return answer;
    }
}

문제를 풀기 위해 생각한 방향

처음 문제를 봤을 때, 1부터 N까지 상자가 차례로 들어오고 트럭에는 주어진 order 순서대로만 실어야 한다는 제약을 확인했다. 컨베이어에서 곧바로 실을 수 없으면 임시로 쌓아두었다가 나중에 꺼내야 하므로, “나중에 넣은 것이 먼저 나온다” 특성을 가진 스택(java.util.Stack) 이 정확히 맞는다고 판단했다.

조건을 분석해 보니 핵심은 두 가지다. 첫째, 컨베이어에서 상자를 하나 받을 때 바로 실을 수 없으면 스택에 push 해야 한다. 둘째, 스택 맨 위가 다음으로 실어야 할 상자와 같다면 맞지 않을 때까지 연속해서 pop 해야 한다. 예제처럼 스택 상단이 연속으로 order와 매칭되는 구간이 생기므로, 단발성 비교가 아니라 while 루프로 가능한 만큼 비우는 패턴 이 필요하다고 보았다.

자료구조 선택은 문제의 LIFO 요구사항에 맞춰 표준 Stack 클래스를 사용했다. 구현 관점에서 필요한 연산은 push, pop, peek, isEmpty 네 가지에 집중하면 충분하다. (Stack 이 동기화 오버헤드가 있더라도 본 문제의 입력 규모에서는 성능 저하가 체감되지 않는다고 판단했다.)

로직 흐름은 다음 불변식을 매 상자마다 유지하도록 설계했다.

1. 컨베이어에서 상자 i를 하나 받는다.
2. 일단 스택에 push(i) 한다.
3. 스택이 비어 있지 않고 스택 맨 위가 order[idx] 와 같다면 while로 연속 pop 하며 실은 개수와 idx를 증가시킨다.
   이 패턴을 유지하면 컨베이어 처리가 끝난 뒤에도 스택에 남은 상자들이 추가로 맞아떨어질 경우를 자연스럽게 처리하게 된다. 또한 모든 비교에서 idx < n 경계 체크를 먼저 수행해 order 범위를 벗어나는 오류를 예방했다.

처음 시도에서는 한 턴에 최대 한 번만 pop 하거나, 메인 루프 종료 후 스택에 남은 상자를 추가로 비우지 않아 누락이 생길 수 있었다. 이를 연속 pop + 종료 후 잔여 스택 처리로 보완해 정답 개수를 정확히 집계하도록 했다.