백준 12789번: 도키도키 간식드리미

학생들이 순서대로 간식을 받아야 하는 상황에서, 순서가 맞지 않는 학생들을 위한 임시 대기 공간을 활용하여 모두가 순서대로 간식을 받을 수 있는지 판별하는 문제입니다. 문제의 상황을 스택(Stack)과 큐(Queue)라는 자료구조로 적절히 모델링하는 것이 핵심입니다.

---

✅ 문제 개요

항목	내용
문제 번호	12789번 - 도키도키 간식드리미
난이도	실버 3
핵심 알고리즘	자료구조, 스택, 큐

---

✅ 문제 설명 요약

• 입력:
  1. 첫째 줄: 학생 수 N (1 ≤ N ≤ 1,000)
  2. 둘째 줄: 현재 서 있는 학생들의 번호표 순서
• 출력: 모든 학생이 순서대로 간식을 받을 수 있다면 "Nice", 그렇지 않다면 "Sad"를 출력
• 규칙:
  • 간식은 1번, 2번, 3번, ... N번 순서대로만 받을 수 있습니다.
  • 현재 줄의 맨 앞에 있는 학생이 자기 순서가 아니면, 한 명씩만 들어갈 수 있는 별도의 대기 공간으로 이동합니다.
  • 대기 공간의 맨 앞에 있는 학생이 자기 순서가 되면 간식을 받을 수 있습니다.

---

✅ 풀이 전략

이 문제의 상황은 두 개의 줄로 모델링할 수 있습니다.

1. 현재 서 있는 줄: 먼저 온 사람이 먼저 나가는 큐(Queue) 구조입니다.
2. 임시 대기 공간: 가장 나중에 들어간 사람이 먼저 나와야 할 수도 있는 스택(Stack) 구조입니다.

이 두 자료구조를 이용하여 간식 배부 과정을 시뮬레이션하면 됩니다.

1️⃣ 자료구조로 상황 모델링

• Queue: 현재 학생들의 대기 줄. ArrayDeque를 사용하여 구현합니다.
• Stack: 순서가 맞지 않는 학생들이 잠시 대기하는 공간. ArrayDeque를 사용하여 구현합니다.
• currentTurn: 현재 간식을 받아야 할 학생의 번호를 저장하는 변수 (1부터 시작).

2️⃣ 알고리즘 설계

1. 학생들의 초기 줄을 Queue에 순서대로 넣습니다.
2. currentTurn을 1로 초기화하고, Stack은 비워둡니다.
3. while 반복문으로 현재 줄(Queue)이 빌 때까지 다음을 반복합니다.
   • Queue의 맨 앞(peek)에 있는 학생이 currentTurn과 일치하면, 간식을 주고 보냅니다. (poll 후 currentTurn 1 증가)
   • Queue의 맨 앞 학생이 currentTurn과 일치하지 않으면, 그 학생을 대기 공간(Stack)으로 보냅니다. (push 후 poll)
4. 현재 줄(Queue)이 모두 비워진 후, Stack에 남아있는 학생들을 처리합니다.
   • while 반복문으로 Stack이 비어있지 않고, Stack의 맨 위(peek)가 currentTurn과 일치하는 동안 학생들을 내보냅니다. (pop 후 currentTurn 1 증가)
5. 모든 과정이 끝난 후, Stack이 비어있다면 모든 학생이 순서대로 간식을 받은 것입니다. "Nice"를 출력합니다.
6. 만약 Stack에 학생이 남아있다면, 순서가 꼬여서 간식을 받지 못한 학생이 있다는 의미이므로 "Sad"를 출력합니다.

예시: 5 4 1 3 2 (N=5)
1. 초기: Queue:[5,4,1,3,2], Stack:[], currentTurn:1
2. Queue 맨 앞 5: currentTurn(1)과 불일치 -> Stack으로 이동.
- Queue:[4,1,3,2], Stack:[5]
3. Queue 맨 앞 4: currentTurn(1)과 불일치 -> Stack으로 이동.
- Queue:[1,3,2], Stack:[5,4]
4. Queue 맨 앞 1: currentTurn(1)과 일치! -> 간식 받음.
- Queue:[3,2], Stack:[5,4], currentTurn:2
5. Queue 맨 앞 3: currentTurn(2)과 불일치 -> Stack으로 이동.
- Queue:[2], Stack:[5,4,3]
6. Queue 맨 앞 2: currentTurn(2)과 일치! -> 간식 받음.
- Queue:[], Stack:[5,4,3], currentTurn:3
7. Queue가 비었으므로 Stack 확인.
- Stack 맨 위 3: currentTurn(3)과 일치! -> 간식 받음. currentTurn:4
- Stack 맨 위 4: currentTurn(4)과 일치! -> 간식 받음. currentTurn:5
- Stack 맨 위 5: currentTurn(5)과 일치! -> 간식 받음. currentTurn:6
8. Stack이 모두 비었음. 최종 결과: Nice

---

✅ Java 코드 예제

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Deque;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 초기 줄은 Queue로 관리
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < N; i++) {
            queue.add(Integer.parseInt(st.nextToken()));
        }

        // 임시 대기 공간은 Stack으로 관리
        Deque<Integer> stack = new ArrayDeque<>();
        
        int currentTurn = 1;

        // 1. 초기 줄(Queue) 처리
        while (!queue.isEmpty()) {
            if (queue.peek() == currentTurn) {
                queue.poll();
                currentTurn++;
            } else {
                stack.push(queue.poll());
            }
        }
        
        // 2. 대기 공간(Stack) 처리
        while (!stack.isEmpty()) {
            if (stack.peek() == currentTurn) {
                stack.pop();
                currentTurn++;
            } else {
                // 스택의 top이 순서와 맞지 않으면 더 이상 진행 불가
                break;
            }
        }

        // 3. 최종 판별
        if (stack.isEmpty()) {
            bw.write("Nice");
        } else {
            bw.write("Sad");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

---

⚠️ 실전 주의사항

항목	설명
자료구조 선택	초기 줄은 FIFO이므로 Queue, 임시 대기 공간은 LIFO이므로 Stack으로 모델링하는 것이 자연스럽습니다. Java의 ArrayDeque는 Queue와 Deque(스택 기능 포함) 인터페이스를 모두 구현하므로 이 문제에 매우 적합합니다.
처리 순서	Queue에서 학생을 꺼내 Stack으로 보내기만 하는 것이 아니라, 매 순간 Stack의 맨 위 학생이 나갈 수 있는지 확인하는 로직을 추가하면 더 효율적으로 처리할 수 있습니다. (예제 코드는 이를 반영하지 않은 더 간단한 구조입니다.)
최종 판별	모든 과정이 끝난 후, Stack이 완전히 비었는지 여부로 성공/실패를 판별하는 것이 가장 명확하고 간단한 방법입니다.
입력 처리	학생들의 번호가 한 줄에 공백으로 구분되어 들어오므로 StringTokenizer를 사용하여 처리해야 합니다.

---

📝 마무리 요약

✔️ 문제의 상황을 자료구조로 모델링하는 능력이 중요합니다 (대기 줄 → Queue, 임시 공간 → Stack).
✔️ 처리해야 할 순번(currentTurn)을 변수로 관리하며, 현재 순번에 맞는 학생이 나올 때까지 학생들을 Queue에서 Stack으로 이동시킵니다.
✔️ Queue가 비워진 후, Stack에 남아있는 학생들이 순서대로 나갈 수 있는지 최종 확인합니다.
✔️ 모든 과정 후 Stack이 비어있으면 성공("Nice"), 학생이 남아있으면 실패("Sad")입니다.