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

프로그래머스

 

 

 

이해하기

• 택배 상자는 1번부터 n번까지 순서대로 컨베이어 벨트에 놓여 전달된다.
• 컨베이어 벨트 = 큐
• 택배 기사님의 배달 순서에 맞춰야 함 = order 배열
• 보조 컨베이어 벨트 = 스택
• 몇 개의 상자를 실을 수 있는지 return

문제를 보았을 때 한 방향으로만 진행되는 컨베이어 벨트는 큐와 같다고 생각하였고, 보조 컨베이어 벨트는 가장 마지막에 보관한 상자부터 꺼낸다는 점에서 스택과 같다고 생각하였다.

 

자료구조까지는 떠올렸지만 문제는 항상 구현...^^

 

1. 일단 큐에 1 ~ n까지 add한다.
2. for문을 돌면서
   1. stack이 비어있다면, order[i]와 queue.peek()이 같다면 꺼내고, 아니라면 stack에 집어넣는다.
   2. stack이 비어있지 않다면, order[i]와 stack.peek()이 같다면 꺼내고, 아니라면 queue.peek()과 비교해본다.
   3. 둘 다 안 되면 break!

 

문제풀이

import java.util.*;

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

                    if (!queue.isEmpty() && queue.peek() == order[i]) {
                        answer++;
                        queue.poll();
                    } else {
                        break;
                    }
                }
            }
        }
        
        
        return answer;
    }
}