[백준12789-자바/우선순위큐] 도키도키 간식드리미

 

위 문제는 글이 매우 길다. 이러한 문제들은 글에서 힌트를 얻을 수 있기 때문에 입력과 출력조건을 읽기전에 천천히 읽어보자.

 

 

이런 힌트를 확인할 수 있다.

이 글을 제대로 읽지 않았다면 홀로 외롭게 재귀문제라고 판단되어 열심히 무한호출 코드를 돌리고있을것이다....(절대 경험담 아님)

 

이 힌트외에는 꼼꼼히 파악해야 할 부분이 하나 더 있다.

해당 순서가 아닌 사람들은 1열로 들어갈 수 있는 공간에 차례대로 집어넣는다.

대기열에서 해당 순번인 사람을 꺼낼 때 해당 순번인지 스택에서도 확인하는 절차가 필요하다.

예를 들어 , 13245 의 입력을 받았다. 대기열에는 13245가 순서대로 서있는것이다.

위 문제대로 풀어보면 다음과 같다.

1. 1번이 바로 입장한다. 3245가 대기열에 있다.

2. 3번은 다음 순서가 아니기때문에 스택에 들어간다. 대기열(245) , 스택(3)

3. 2번 순서는 대기열에 있기 때문에 2를 입장시킨다. 대기열(45) 스택(3)

4. 3번 순서는 대기열이 아닌 스택에 있다. 스택에서 3을 입장시킨다. 대기열(45) << 이 과정을 가장 많이 빼먹는 부분
...
5. 순서대로 4,5가 입장한다.

 

절차는 아래와 같다.

1. 문제를 자세히 읽고 힌트 파악

2. 입력에서 학생들의 수를 파악한다. N은 최대 1000이다. 모든 입력을 한 번씩만 순회하면 되기에 O(N)의 시간복잡도를 갖는다.

3. 대기열과 1열로 들어갈수 있는 공간을 만들어서 조건에 맞게 코드를 구현해준다.

package Stack;

import java.util.*;

public class StackP12789 {
    static int N;
    static Queue<Integer> list ;
    static Stack<Integer> st ;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        /*
         *   현재 줄 서있는곳  (Queue)
         *    한 명씩 서 있을 수 있는 곳 (Stack)
         *
         *   1. 현재 줄 서 있는곳의 인원을 모두 빼서 1부터 차례대로 입장
         *   2. 순서가 아닌 사람들은 Stack으로 이동
         *   3. Stack에서 순서대로 입장(순서대로 입장이 안되면 Sad)
         *
         *  실수한 점
         *  2번에서 이동 후 stack에 이미 사람이 있다면 stack에서도 번호가 일치하는지 추가로 확인해야함
         * */

        N = sc.nextInt();
        list = new LinkedList<>();
        st = new Stack<>();



        for (int i = 0; i < N; i++) {
            list.add(sc.nextInt());
        }

        int idx = 1;
        while (list.size() != 0) {
            if(list.peek()==idx) {
                list.poll();
                idx++;

            }else if(!st.isEmpty() && st.peek() == idx){
                st.pop();
                idx++;
            }

            else {
                st.push(list.poll());
            }
        }

        while (!st.isEmpty()) {
            if (st.peek() == idx) {
                st.pop();
                idx++;
            }
            else{
                break;
            }
        }

        System.out.println(st.isEmpty()?"Nice" : "Sad");

    }
}