[programmers] 택배상자 - Java

택배상자

문제 설명

제한사항

• 1 ≤ order의 길이 ≤ 1,000,000

• order는 1이상 order의 길이 이하의 모든 정수가 한번씩 등장합니다.

• order[i]는 기존의 컨테이너 벨트에 order[i]번째 상자를 i+1번째로 트럭에 실어야 함을 의미합니다.

입출력 예

입출력 예 설명

• 문제 예시와 같습니다.

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

solution.java

import java.util.*;

class Solution {
    public int solution(int[] order) {
        Stack<Integer> stack = new Stack<>(); // 보조 컨테이너 벨트
        int currentBox = 1; // 컨테이너 벨트의 다음 상자
        int loadedCount = 0; // 성공적으로 실은 상자 수
        
        for (int targetBox : order) {
            // 원하는 상자에 도달하거나 다 꺼낼 때까지 반복
            while (currentBox <= order.length && currentBox < targetBox) {
                stack.push(currentBox);
                currentBox++;
            }
            
            // 현재 컨테이너 벨트의 상자가 원하는 상자인 경우 실는다
            if (currentBox == targetBox) {
                loadedCount++;
                currentBox++;
            }
            // 아니라면 원하는 상자가 보조 스택의 상단에 있는지 확인
            else if (!stack.isEmpty() && stack.peek() == targetBox) {
                stack.pop();
                loadedCount++;
            }
            // 두 조건 모두 충족되지 않으면 상자를 실을 수 없음
            else {
                break;
            }
        }
        
        return loadedCount;
    }
}

핵심 키워드

• 컨테이너 벨트의 현재 상자가 order 배열의 목표 상자보다 작으면 목표 상자에 도달할 때까지 스택에 밀어 넣는다.

• 스택 상단에 있는 상자가 원하는 상자인 경우 스택에서 해당 상자를 pop하고 카운트를 증가시킨다.

• 벨트나 스택에 원하는 상자가 없으면 적재를 중지한다.

결론!