프로그래머스 택배상자 자바 풀이

문제 링크

문제 요약

order 배열은 택배 기사님이 원하는 상자 적재 순서다
기존 컨테이너 벨트는 1번부터 순서대로만 꺼낼 수 있다
보조 벨트는 스택처럼 마지막에 넣은 것부터 꺼낼 수 있다
원하는 순서대로 최대한 실을 수 있는 상자 개수를 구하는 문제다

문제 풀이

처음에는 기존 벨트를 실제 리스트로 만들어 놓고, 맨 앞 원소를 계속 꺼내 보조 벨트에 쌓았다가 필요할 때 꺼내는 식으로 그대로 시뮬레이션하면 되겠다고 생각했다.

하지만 리스트에서 맨 앞 원소를 지우면 뒤에 있는 원소들이 한 칸씩 당겨지면서 그 자체로 O(n)이 걸린다.

order의 길이가 최대 1,000,000인데 이 과정을 매번 반복하면 최악의 경우 O(n²)이 되어 시간 안에 끝나지 않는다.

이 문제의 핵심은 기존 벨트에서 실제로 상자를 옮길 필요 없이, 다음에 꺼낼 번호(next)만 변수로 추적하면 된다는 점이다.

order[i]가 next보다 크면, next부터 order[i] 전까지는 아직 실을 차례가 아닌 상자들이므로 보조 벨트(스택)에 순서대로 쌓는다
order[i]가 next와 같으면 바로 실을 수 있으므로 next를 하나 늘리고 answer도 늘린다
그렇지 않다면 보조 벨트 맨 위와 order[i]를 비교해서, 같으면 꺼내서 싣고 다르면 더 이상 실을 수 없으므로 멈춘다

이때 보조 벨트는 마지막에 넣은 상자부터 나오기 때문에 Deque의 뒤쪽(peekLast, pollLast)만 사용하면 스택처럼 동작한다.

최종 코드

java

import java.util.*;

class Solution {
    public int solution(int[] order) {
        int answer = 0;
        
        Deque<Integer> stack = new ArrayDeque<>(); // 보조 컨테이너 벨트 역할
        int max = order.length;
        int next = 1; // 다음에 실어야 할 상자 번호
        
        for(int i=0;i<order.length;i++){
            int now = order[i];
            // next부터 now 전까지는 아직 실을 차례가 아니므로 보조 벨트에 쌓아둔다
            while(next < now){
                stack.offerLast(next++);
            }
            
            if(next == now){
                answer++;
                next++;
                continue;
            }
            
            // 보조 벨트 맨 위와 다르면 더 이상 원하는 순서대로 실을 수 없다
            if (stack.isEmpty() || stack.peekLast() != now) {
                break;
            }
            
            stack.pollLast();
            answer++;
        }
        return answer;
    }
}

택배상자

문제 요약

문제 풀이

최종 코드

함께 읽으면 좋은 글

롤케이크 자르기

할인 행사

숫자 변환하기

두 원 사이의 정수 쌍