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

 

문제

프로그래머스

 

알고리즘

큐, 스택, 해시셋

 

풀이

택배를 옮기는 흐름은 다음과 같다.

 

1. 원하는 택배가 기존 컨테이너 벨트에 있다면

원하는 택배를 찾을 때까지 기존 컨테이너 벨트의 택배들을 보조 컨테이너에 담는다.

 

2. 원하는 택배가 보조 컨테이너 벨트에 있다면

(1) 보조 컨테이너 벨트의 맨 앞에 있다면 꺼낸다.

(2) 보조 컨테이너 벨트의 맨 앞에 있지 않다면 더 이상 작업을 진행할 수 없다.

 

이를 구현하기 위해

1부터 순서대로 올려져있는 기존 컨테이너 벨트는 큐를

기존 컨테이너에서 옮긴 역순으로 올려져있는 보조 컨테이너 벨트는 스택을 사용하고

보조 컨테이너에 있는 지 빠르게 확인하기 위해 해시셋을 사용한다.

---

 

해당 자료구조를 이용해 위의 흐름을 다시 옮기면 다음과 같다.

 

1. 원하는 택배 o가 set에 없다면(기존 컨테이너 벨트에 있다면)

찾을 때까지 기존 컨테이너(큐) 벨트의 택배들을 꺼내 보조 컨테이너 벨트(스택)에 옮긴다.

찾으면 큐에서 제거한다.

 

1. 원하는 택배 o가 set에 있다면(보조 컨테이너 벨트에 있다면) 

(1) stack.peek() == o 라면 stack에서 꺼내고, set에서 제거

(2) stack.peek() != o 라면 더 이상 작업이 불가능하므로 프로그램 종료

 

 

 

코드

import java.util.*;

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