택배상자

문제

영재는 1번부터 n번까지 번호가 증가하는 순서대로 메인 컨베이어 벨트에서 전달되는 택배상자를 트럭에 실어야 합니다. 단, 택배 기사님이 미리 알려준 순서(order)에 맞게 실어야 합니다. 순서가 맞지 않는 상자는 보조 컨베이어 벨트에 임시로 보관할 수 있습니다. 보조 컨베이어 벨트는 맨 앞의 상자만 뺄 수 있는 구조(LIFO, 스택)입니다. 보조 컨베이어 벨트를 이용해도 기사님이 원하는 순서대로 상자를 싣지 못한다면 작업을 중단합니다. 이때 영재가 트럭에 실을 수 있는 상자의 최대 개수를 구하는 문제입니다.

• 입력: 택배 기사님이 원하는 상자 순서를 나타내는 정수 배열 order (길이 1 이상 1,000,000 이하)
• 출력: 영재가 트럭에 실을 수 있는 택배상자의 개수를 반환합니다.

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

풀이: Stack을 활용한 직관적인 시뮬레이션

메인 컨베이어 벨트에서 들어오는 상자 번호(1부터 n까지)를 기준으로 순차적으로 탐색하며, 스택을 통해 보조 컨베이어 벨트를 모사하는 풀이입니다.

• 보조 벨트(Stack) 활용: 메인 벨트에서 상자(i)가 들어오면, 일단 보조 벨트(스택)에 넣습니다(st.push(i)).
• 트럭 상차 조건 확인: 스택의 맨 위 상자(st.peek())가 현재 트럭에 실어야 하는 상자(order[idx])와 일치하는지 확인합니다.
  • 일치한다면 상자를 트럭에 싣습니다(st.pop()).
  • 상자를 실었으므로 트럭의 다음 순서로 넘어갑니다(idx++).
  • 새로 스택의 맨 위가 된 상자도 연달아 실을 수 있는지 확인하기 위해 while문으로 반복 처리합니다.
• 결과 도출: 1번부터 n번 상자까지 모두 지나가고 나면, 트럭에 상차한 횟수이자 다음으로 실어야 할 순서의 인덱스인 idx 자체가 정답이 됩니다.

코드

import java.util.*;

class Solution {
    public int solution(int[] order) {
        int idx = 0;
        Stack<Integer> st = new Stack<>();
        
        // 메인 컨베이어 벨트에서 1번부터 order.length번 상자까지 순차적으로 들어옴
        for (int i = 1; i <= order.length; i++) {
            // 일단 보조 컨베이어 벨트(스택)에 넣음
            st.push(i);
            
            // 보조 벨트 맨 앞의 상자가 현재 실어야 할 순서와 일치하면 계속해서 뺌
            while (!st.isEmpty() && st.peek() == order[idx]) {
                st.pop(); // 상자를 트럭에 실음
                idx++;    // 다음 실어야 할 상자 순서로 넘어감
            }
        }
        
        // 최종적으로 실은 상자의 개수 반환
        return idx;
    }
}

알고리즘 분류

자료 구조 (Data Structures), 스택 (Stack), 시뮬레이션 (Simulation)