프로그래머스_택배상자_day14

 

알고리즘 챌린지 14일 차이다. 사실 어제 포스팅을 했어야 했지만, 어제는 지방에 당일 출장을 갔다가 올라와서 바로 기절해 버렸다.. 아예 넘길 순 없으니 오늘은 문제 두 개를 풀고자 한다. 

프로그래머스 Level2 택배상자 문제로 정답률은 55%인 준수한 문제이다. 

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

프로그래머스

 

택배가 나오는 메인 컨테이너 벨트는 FIFO구조로 나오게 되고, 택배를 트럭에 싣는 우선순위가 존재한다. 
택배를 임시로 저장할 예비 컨테이너가 있지만, 해당 컨테이너는 입구에서만 꺼낼 수 있는 FILO 구조다. 

대충 문제를 쭉 읽어보니 자료구조만 잘 선택해서 풀이하면 되겠다라고 생각을 해서 가장 먼저 우선순위 큐를 생각해 보았다. 하지만, order배열에 초기화된 순서를 제외하고는 우선순위를 판단할 기준이 없기 때문에 다른 방법을 생각해 보았고, 
메인 컨테이너는 택배 상자의 번호가 커지는 순서로 차례대로 나오고 꺼내면 끝이기 때문에, 자료구조를 따로 사용하지 않고, 임시로 저장할 수 있는 서브 컨테이너만 스택 자료 구조를 사용하기로 했다. 

메인 로직은 아래와 같다. 

0. 이번에 택배를 싣는 순서를 저장할 target변수를 생성한다.(배열 인덱스 편의를 위해 0부터 시작하자. )
- 나중에 target값을 트럭에 싣은 상자수로 카운트 할 수 있다. 

1. order 배열을 순회하면서 우선순위 배열을 초기화한다. 
- ex, 첫 번째로 나와야 하는 값이 4라면 배열[4-1] = 0을 초기화해준다. 
- 완성된 배열의 인덱스가 택배상자의 번호가 될 것이고, 배열의 값은 택배상자가 실려야 하는 순서를 나타내게 될 것이다. 

2. 컨테이너에서 나오는 순서대로 택배를 꺼내면서 이번에 실어도 되는 택배인지 판단한다. 
- 1번 상자부터 나올텐데, 1번 상자를 실어야 하는 순서(우선순위배열[0])가 이번에 실어야 하는 택배 번호(target)와 동일한 경우에만 택배를 싣고 target값을 올려준다. 
- 실을 수 없는 경우는 서브 컨테이너에 잠시 보관하고 다음 순서로 넘어간다. 
- 매 반복마다, 스택을 순회하면서 스택에 최상단에 이번에 실어야 하는 택배 상자가 있는 경우에만 꺼내서 트럭에 싣는다.

인덱스로 인해서 조금 헷갈릴수도 있을 것 같아서 실행로직을 간단하게 그림으로 첨부할 테니 참고해서 이해해 보길 바란다.

i == 0인 경우 

i == 1인 경우

i == 2인 경우

i == 3인 경우

i == 4인 경우는 위의 로직대로 그대로 따라가다 보면 조건에 만족하는 부분이 없어서 더 이상 택배를 싣지 못하고, 
반복이 끝나 종료된다. 마지막 순간의 target값 2를 리턴하면 정답이다.

 

Java

import java.util.*;
import java.util.stream.*;
class Solution {
    public int solution(int[] order) {

        Stack<Integer> subContainer = new Stack<>();
        int [] priority = new int[order.length];

        for(int i=0; i<order.length; i++){
            priority[order[i]-1] = i;
        }
        
        //현재 박스에 실어야 하는 순서를 표기할 target변수
        int target = 0;
        for(int i=0; i<order.length; i++){
            if(priority[i] == target) target++;
            else subContainer.push(priority[i]);
            
            while(!subContainer.isEmpty() && subContainer.peek() == target) {
                subContainer.pop();
                target++;
            }
            
        }
        return target; 
    }
}