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

프로그래머스

접근 방식

처음에는 order 배열에 들어있는 숫자들이 곧 박스의 우선순위라고 생각했으나 알고보니 우선순위는 order의 인덱스 순서이고 order배열의 숫자는 해당 우선순위 박스의 위치를 가리키고 있었다. 그렇기에 order를 참고하여 박스가 올라가있는 메인 컨베이어 벨트를 priority 배열에 별도로 구현한 후에 문제에서 제시한대로 로직을 수행했다. 보조 컨테이너의 동작 방식은 LIFO이므로 스택으로 선언하여 관리했다. 

로직 설명

- order로부터 실제 박스가 놓인 priority 배열 구현

- 보조 컨베이어벨트를 표현할 stack 선언

- 현재 트럭에 실어야하는 순서를 표기할 target 변수 선언

- 박스가 놓인 메인 컨베이어벨트 priority 배열을 탐색하며:

  1) 현재 박스가 target인 경우 트럭에 싣기(target 증가) 

  2) 아닌 경우 보조 컨베이어벨트에 넣기

  3) 보조 컨테이너 stack에 박스가 존재하고 실어야하는 순서라면 트럭에 싣기 (pop() 후 target 증가)

  4) target 반환 (target = 트럭에 실린 총 박스 개수와 동일)

import java.util.*;

class Solution {
    public int solution(int[] order) {
        int answer = 0;
        int[] priority = new int[order.length];
        
        for(int i = 0; i < order.length; i++){
            priority[order[i] - 1] = i;
        }
        
        Stack<Integer> stack = new Stack<>();
        
        int target = 0;
     
        for(int i = 0; i < priority.length; i++){
            if(priority[i] == target){
                target++;
            }else{
                stack.push(priority[i]);
            }
            while(!stack.isEmpty() && stack.peek() == target){
                stack.pop();
                target++;
            }
        }
        return target;
    }
}

Note

- 메인 컨베이어 벨트인 priority 배열을 굳이 따로 선언하지 않고도 바로 작업한 풀이들도 있기는 했는데 문제와 직관적으로 매치되는지는 잘 모르겠다. 물론 배열 할당에 필요한 메모리조차 아껴야하는 상황이라면 고민을 더 했겠지만 다른 문제에서도 그랬듯 나는 명시적으로 코드에 의도가 드러나는 쪽을 더 선호하기에 이 방식이 더 좋다고 생각한다.