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

코드 힌트

1. 순서 확인:
   • 1번 상자부터 시작하여 order 배열의 원하는 순서대로 상자를 트럭에 싣는 것이 목표입니다.
   • 상자를 순서대로 트럭에 실을 수 있는지 확인하며 진행합니다.
2. 스택 사용:
   • 만약 현재 상자를 바로 트럭에 실을 수 없을 경우, 스택을 사용하여 임시로 상자를 저장합니다.
   • 스택은 LIFO(Last In, First Out) 구조를 가지며, 가장 나중에 넣은 상자를 먼저 꺼낼 수 있습니다.
3. 스택과 비교:
   • 스택에 상자가 쌓인 상태에서, 현재 순서에 맞는 상자가 스택의 맨 위에 있다면, 스택에서 상자를 꺼내 트럭에 실습니다.
   • 만약 스택의 맨 위 상자가 현재 순서에 맞지 않으면, 상자를 더 이상 실을 수 없으므로 반복을 종료합니다.
4. 결과 반환:
   • 최종적으로 트럭에 실을 수 있는 최대 상자 개수를 계산하여 반환합니다.
   • 이를 통해 상자를 순서대로 실을 수 있는 최대 수를 확인할 수 있습니다.

 

 

 

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    public int solution(int[] order) {
        int result = 0;  // 상자를 트럭에 실은 개수를 저장하는 변수
        int idx = 0;  // order 배열에서 다음에 실어야 할 상자의 인덱스를 나타냄
        
        Stack<Integer> stack = new Stack<>();  // 임시로 상자를 저장할 스택
        
        // 1번 상자부터 order 배열의 길이만큼 반복
        for (int i = 1; i <= order.length; i++) {
            // 현재 상자가 order[idx]와 일치하면 바로 트럭에 실음
            if (order[idx] == i) {
                result++;  // 트럭에 실은 상자 개수 증가
                idx++;  // 다음 상자를 가리키도록 인덱스 증가
            } 
            // 스택의 맨 위 상자가 order[idx]와 일치하면 스택에서 꺼내어 트럭에 실음
            else if (!stack.isEmpty() && stack.peek() == order[idx]) {
                stack.pop();  // 스택에서 상자 제거
                idx++;  // 다음 상자를 가리키도록 인덱스 증가
                result++;  // 트럭에 실은 상자 개수 증가
                i--;  // i를 다시 반복하기 위해 감소
            } 
            // 그렇지 않으면 스택에 상자를 쌓음
            else {
                stack.add(i);  // 스택에 상자 추가
            }
        }
        
        // 남아있는 스택의 상자들을 처리
        while (!stack.isEmpty()) {
            // 스택의 맨 위 상자가 order[idx]와 일치하면 트럭에 실음
            if (stack.peek() == order[idx]) {
                stack.pop();  // 스택에서 상자 제거
                result++;  // 트럭에 실은 상자 개수 증가
                idx++;  // 다음 상자를 가리키도록 인덱스 증가
            } else {
                break;  // 더 이상 맞는 순서가 없으면 종료
            }
        }
        
        return result;  // 트럭에 실을 수 있는 최대 상자 개수를 반환
    }
}