[C#] 12789번: 도키도키 간식드리미

목차

---

백준 단계별로 풀어보기

25.11.18

16단계: 스택, 큐, 덱 1

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

문제 링크 : https://www.acmicpc.net/problem/12789

 

문제를 풀기 위해 알아야 할 개념

>> Queue

: 아래 글에 정리해두었다.

 

자료구조

 

문제 풀이

: 현재 줄 서있는 곳은 먼저 넣은 수가 먼저 나와야 하므로 Queue로, 한 명씩만 설 수 있는 공간은 마지막에 넣은 수가 먼저 나와야 하므로 Stack으로 관리한다. 순서대로 간식을 받을 수 없는 상황은 Stack의 중간에 다음 간식을 받을 사람이 있는 경우 밖에 없다. Queue에 수가 남아있을 경우 Stack으로 Push 하기 때문에 Queue는 비어있고 Stack을 Peek 했을 때 다음 순서가 아니라면 순서대로 간식을 받을 수 없는 상황이다.

1. StreamReader로 입력값을 받아 int값으로 변환하여 현재 승환이의 앞에 서 있는 학생들의 수를 담을 변수 n 에 담고, 승환이의 앞에 서있는 모든 학생들의 번호표를 입력받아 input 에 담고, 현재 줄 서 있는 곳을 담을 int형 Queue queue 와 한 명씩만 설 수 있는 공간을 담을 int형 Stack stack 을 초기화하고, 순서대로 받을 번호를 담을 변수 num 을 1로 초기화한다.
2. for 반복문을 통해 input 의 값을 하나씩 int로 변환하여 Queue 에 담는다.
3. while 반복문을 통해 Queue와 Stack의 Count가 모두 0일 때까지 아래 과정을 반복하여 간식을 순서대로 받을 수 있는지 확인한다.
   •     Queue에 수가 남아있고, Queue의 맨 앞 요소가 num 과 같다면 Queue의 요소를 빼고 num 을 1 증가시킨다.
   •     Stack에 수가 남아있고, Stack의 맨 위 요소가 num 과 같다면 Stack의 요소를 빼고 num 을 1 증가시킨다.
   •     Queue와 Stack을 Peek한 값이 num 과 다르고 Queue에 요소가 남아있다면, Queue의 요소를 빼서 Stack에 Push한다.
   •     위의 모든 과정에 해당되지 않는다면 즉, Queue는 비어있는데, Stack의 맨 위 요소가 num 과 다르다면 순서대로 간식을 받을 수 없는 상황이므로 "Sad" 를 출력하고 return 한다.
4. while 반복문을 빠져나왔다면 순서대로 간식을 받을 수 있는 상황이므로 "Nice" 를 출력한다.

 

정답 코드

using System.IO;

class Backjoon
{
    static void Main(string[] args)
    {
        using var sr = new StreamReader(Console.OpenStandardInput());
        using var sw = new StreamWriter(Console.OpenStandardOutput());

        int n = int.Parse(sr.ReadLine());
        string[] input = sr.ReadLine().Split();
        Queue<int> queue = new Queue<int>();
        Stack<int> stack = new Stack<int>();
        int num = 1;

        for (int i = 0; i < n; i++)
        {
            queue.Enqueue(int.Parse(input[i]));
        }

        while (queue.Count > 0 || stack.Count > 0)
        {
            if (queue.Count > 0 && queue.Peek() == num)
            {
                queue.Dequeue();
                num++;
            }
            else if (stack.Count > 0 && stack.Peek() == num)
            {
                stack.Pop();
                num++;
            }
            else if (queue.Count > 0)
            {
                stack.Push(queue.Dequeue());
            }
            else
            {
                sw.Write("Sad");
                return;
            }
        }
        sw.Write("Nice");
    }
}