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

스택을 활용해 메인 벨트와 보조 벨트의 흐름을 시뮬레이션하는 문제

 

1. 문제 유형

스택, 구현, 시뮬레이션

 

2. 내가 놓친 포인트

처음 떠올린 접근 : 박스를 미리 메인 벨트용 / 보조 벨트용으로 분류해서 처리하려고 했다.

오답 원인: 박스를 미리 분류하는 문제가 아니라, 1번부터 n번까지 순서대로 들어오는 박스를 그때그때 현재 목표와 비교하며 처리하는 시뮬레이션 문제였다.

 

3. 핵심 로직 & 해결 방법

핵심 조건: 보조 컨테이너 벨트는 스택처럼 동작하므로 가장 최근에 넣은 박스만 꺼낼 수 있다.

풀이 아이디어:

1. 메인 벨트에서는 1번부터 n번 박스가 순서대로 들어온다.
2. 현재 들어온 박스가 지금 실어야 하는 목표 박스라면 바로 적재한다.
3. 아니라면 보조 벨트(stack)에 넣는다.
4. 이후 보조 벨트 top이 현재 목표와 같을 동안 계속 꺼내서 적재한다.
5. 더 이상 목표 박스를 꺼낼 수 없으면 그 시점에서 종료된다.

4. 구현 코드

import java.util.*;

class Solution {
    public int solution(int[] order) { 
        // 1. 보조 컨테이너 벨트 생성
        Deque<Integer> stack = new ArrayDeque<>();  
             
        int result = 0;
        int currentTarget = 0; 
        
        // 2. 메인 벨트에서 1번부터 n번까지 순서대로 확인
        for(int i = 1; i <= order.length; i++) {
            // 2-1. 현재 박스가 바로 실어야 하는 박스면 적재
            if(currentTarget < order.length && i == order[currentTarget]) {
                result++;
                currentTarget++;
            } else {
                // 2-1-1. 아니면 보조 벨트에 보관
                stack.push(i);
            }
            
            // 2-2. 보조 벨트 top이 현재 목표와 같으면 계속 꺼내서 적재
            while(!stack.isEmpty()) {
                if(order[currentTarget] == stack.peek()) {
                    stack.pop();
                    result++;
                    currentTarget++;
                } else {
                    break;
                }
            }
        }
        return result;
    }
}

시간 복잡도: O(N) / 공간 복잡도: O(N)

---

 

인사이트

• while (!stack.isEmpty()) 안에서 order[currentTarget]를 바로 읽는 부분은 처음엔 범위 초과가 날 것 같다고 생각했는데, 이 문제에서는 모든 박스를 다 실은 순간 stack도 비어 있어야 한다는 흐름 때문에 실제로는 안전하게 동작한다는 점 배웠다.

 

 

문제 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/131704