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

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

프로그래머스

 

문제 설명

실어야 하는 택배상자가 (1~n번까지) 번호가 증가하는 순서대로 컨테이너 벨트에 일렬로 놓여 전달됩니다.  컨테이너 벨트는 한 방향으로만 진행 -> 벨트에 놓인 순서대로(1번 상자부터) 상자를 내릴 수 있습니다. //   1 2 3 4 5 ...

하지만 트럭에 실을 때에는 order순서에 맞춰 넣어야 합니다.

컨테이너 벨트 맨 앞의 놓인 상자가 현재 트럭에 실어야 하는 순서가 아니라면 그 상자를 보조 컨테이너 벨트에 넣어야 합니다. 보조 컨테이너는 다른 면이 막혀 있어서 맨 앞의 상자만 뺄 수 있다(즉, 가장 마지막에 보조 컨테이너 벨트에 넣었던 상자부터 꺼내게 됩니다.)

보조 컨테이너 벨트를 이용해도 기사님이 원하는 순서대로 상자를 싣지 못한다면, 더 이상 상자를 싣지 않습니다.

택배 기사님이 원하는 상자 순서를 나타내는 정수 배열 order가 주어졌을 때, 몇 개의 상자를 실을 수 있는지 return 하는 solution 함수를 완성하세요.

---

💡 아이디어

보조 컨테이너는 다른 면이 막혀 있어서 마지막에 넣었던 상자만 꺼낼 수 있기 때문에 Stack을 사용해 보조 컨테이너 벨트를 구현했습니다.

 

📗 풀이과정

1. Stack을 선언해 보조 컨테이너 벨트를 만들어 줍니다.

또한 현재 몇 번째 박스까지 실었는지 저장하기 위해 orderIdx도 선언합니다.

Stack<Integer> stack = new Stack<>(); //보조 컨테이너

int orderIdx = 0;//몇 번째 박스를 실어야 하는지

 

2. 컨테이너 벨트에서 박스를 하나씩 받으면서 현재 실어야 하는 박스라면, 트럭에 싣고 answer에 추가합니다.

또 다음 박스 순서를 확인해야 하기 때문에 orderIdx도 1을 더해 다음 순서를 나타내도록 합니다.

for(int i=1;i<=order.length;i++){
	//컨테이너 벨트 위의 박스와 현재 순서의 박스인지 확인
    if(i==order[orderIdx]){
    	answer++; //트럭에 실음
        orderIdx++;//다음 순서의 박스 index
    }

 

3. 만약 현재 컨테이너 벨트에 전달된 박스가 실어야 하는 박스 순서와 같지 않다면, 해당 박스를 보조 컨테이너(stack)에 넣습니다.

else{
	stack.push(i);
}

 

4. 2,3번 작업이 끝난 후 다음 작업에 넘어가기 전, 보조 컨테이너 벨트 안에서 트럭에 실을 수 있는 박스는 모두 꺼내고 다음 작업을 수행하도록 합니다.

//스택의 마지막에 넣었던 박스와 현재 실어야하는 박스가 같을 때 박스를 모두 싣는다
while(!stack.isEmpty() && stack.peek()==order[orderIdx]){
	orderIdx++;
    answer++;
    stack.pop();
}

 

5. 컨테이너 벨트에서 모든 박스를 받을 때까지 반복하고, 실을 수 있는 박스의 개수 answer를 return 합니다.

 

---

전체 코드

import java.util.*;
class Solution {
    public int solution(int[] order) {
        int answer = 0;
        
        Stack<Integer> stack = new Stack<>();
        int orderIdx=0;//몇 번째 박스까지 실었는지
        
        for(int i=1;i<=order.length;i++){
            
            //컨테이너 벨트위의 박스와 order박스가 같은지
            if(i==order[orderIdx]){
                answer++;
                orderIdx++;
            }else{//다르면
                stack.push(i);
            }
            
            //스택에서 마지막 박스와 order박스가 같은지
            while(!stack.isEmpty() && stack.peek()==order[orderIdx]){
                orderIdx++;
                answer++;
                stack.pop();
            }
        }
        
        return answer;
    }
}