[백준/C# (.NET)] 10845번 큐

 

백준 온라인 저지 / 10845번 큐

https://www.acmicpc.net/problem/10845

10845번: 큐

 

• 사용언어 : C# (.NET)
• 알고리즘 : 자료 구조, 큐

 

 

 

C#코드

1. 문제 정리

 

이번 문제는 테스트 케이스 값을 받아와 그 값만큼 명령어를 받아오는 문제이다.

전에 풀어 봤던 스택과 다를 게 없는 문제이다. 그때 스택을 잠깐 살펴보았을 때 스택은 LIFO 후입 선출이라고 칭했지만,

큐는 그와 반대인 선입 선출 FIFO의 개념과 같다.

 

이 문제도 solved.ac 기준 클래스 2에 있는 문제이다. 자료 구조의 쌩 기초라고 보면 편하다.

 

문제를 살펴보자.

 

스택 명령어	description
push X	정수 X를 큐에 넣는 연산이다.
pop	큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size	큐에 들어있는 정수의 개수를 출력한다.
empty	큐가 비어있으면 1, 아니면 0을 출력한다.
front	큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back	큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

 

스택 문제와 다른 것이 있다면 큐의 가장 뒤에 있는 정수를 출력하는 back 명령어와 앞의 정수를 출력하는 front가 다르다. 

 

사실상 스택에서의 top과 큐에서의 front가 같다고 볼 수 있으니 back 하나가 추가되었다고 볼 수 있겠구나...

그렇다면 큐에 대해서 잠깐 짚고 넘어 가보자

 

 

2. 큐란 무엇일까?

 

문제 이름부터 큐인데 큐를 모르고 지나가면 또 안된다...

스택 큐 덱까지 다음에 프로그래밍 노트에 정리하도록 하고 간단하게 알아보자.

 

 

namu,wiki에서 발췌

 

일단 스택과 큐는 후입 선출 선입선출에서 차이가 있다고 말했다. 사실상 이거 말곤 명령어 차이? ㅋㅋ 그 차이뿐이다.

 

일단 이해를 위해서 스택 문제 글에서 스트링 빌더와 네임 스페이스 등을 참고하길 바란다.

https://www.jongung.com/23

[백준/C# (.NET)] 10828번 스택

 

push가 데이터를 입력 pop이 데이터를 빼오는 것이었는데 큐에서는 Enqueue가 데이터를 넣는 거고 Dequeue가 데이터를 빼는 명령어이다. 이는 C#에서도 똑같이 작용한다.

 

자세히 알아보고 싶다면 

 

C# 큐 클래스

Queue 클래스 (System.Collections.Generic)

 

3. C#에서의 큐

 

C#에서 큐를 사용해볼 건데 문제에서 총 6개의 명령어가 있었다.

 

Push, Pop, size. empty, front, back

 

C# 공식 문서를 읽어보자.

 

 

Collections.Generic을 쓰면 된다고 한다. 제너릭을 써야 하는 이유는 스택 글을 참고하십쇼..

 

using System.Collections.Generic;

Queue<int> queue = new();

인트형 queue를 만들어주고 

문제에서 하라는 대로 진행했다.

 

var A = int.Parse(Console.ReadLine());
            Queue<int> queue = new();
            StringBuilder sw = new();

            for (int i = 0; i < A; i++)
            {
                string[] input = Console.ReadLine().Split(' ');


                if (input[0] == "push")
                {
                    queue.Enqueue(int.Parse(input[1]));
                }
                else if (input[0] == "pop")
                {
                    if (queue.Count == 0)
                    {
                        sw.AppendLine("-1");
                    }
                    else
                    {
                        sw.Append(queue.Dequeue() + "\n");
                    }
                }
                else if (input[0] == "size")
                {
                    sw.Append(queue.Count + "\n");
                }
                else if (input[0] == "empty")
                {
                    if (queue.Count == 0)
                    {
                        sw.AppendLine("1");
                    }
                    else
                    {
                        sw.AppendLine("0");
                    }
                }
                else if (input[0] == "front")
                {
                    if (queue.Count == 0)
                    {
                        sw.AppendLine("-1");
                    }
                    else
                    {
                        sw.Append(queue.Peek() + "\n");
                    }
                }
                else if (input[0] == "back")
                {
                    if (queue.Count == 0)
                    {
                        sw.AppendLine("-1");
                    }
                    else
                    {
                        sw.Append(queue.??() + "\n");
                    }
                }

 

자 여기서 나는 의문이 들었다.. 아니 큐의 맨 앞을 찾는 peek()는 있다고 쳐... 근데 back은 뭘로 찾아?

 

뭐 어떻게 찾긴 못 찾아.. 그래서 idx1,2를 만들어서 앞 뒤를 인덱스로 찍어 보려고도 노력해봤는데 딱히 되진 않았고... 구글링을 하던 도중 알아냈다.

 

 

4. Linq

 

잊을만하면 나타나는 Linq인데.. 진짜 자주 사용하긴 하나 보다 ㅋㅋ... (C#도 bit/stdc++ 없나요?)

 

여기서 사용할 함수는 바로 Last이다.

queue.Last로 작성하면 맨 뒤를 읽어 준다는 것이다.

 

The value at the last position in the source sequence

 

이거는 Linq에서만 작동하는 함수인데 왜 따로 컬렉션 제너릭에 안 만들어 놨을까? 당연히 없어도 되는 거니깐 그랬겠지 뭐...

 

back은 그래서 Last로 구현하고 스트링 빌더로 작성해주면 해결 가능 한 문제이다...

 

 

5. 완성 코드

 

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace boj
{
    class Program
    {
        static void Main(string[] args)
        {
            var A = int.Parse(Console.ReadLine());
            Queue<int> queue = new();
            StringBuilder sw = new();

            for (int i = 0; i < A; i++)
            {
                string[] input = Console.ReadLine().Split(' ');


                if (input[0] == "push")
                {
                    queue.Enqueue(int.Parse(input[1]));
                }
                else if (input[0] == "pop")
                {
                    if (queue.Count == 0)
                    {
                        sw.AppendLine("-1");
                    }
                    else
                    {
                        sw.Append(queue.Dequeue() + "\n");
                    }
                }
                else if (input[0] == "size")
                {
                    sw.Append(queue.Count + "\n");
                }
                else if (input[0] == "empty")
                {
                    if (queue.Count == 0)
                    {
                        sw.AppendLine("1");
                    }
                    else
                    {
                        sw.AppendLine("0");
                    }
                }
                else if (input[0] == "front")
                {
                    if (queue.Count == 0)
                    {
                        sw.AppendLine("-1");
                    }
                    else
                    {
                        sw.Append(queue.Peek() + "\n");
                    }
                }
                else if (input[0] == "back")
                {
                    if (queue.Count == 0)
                    {
                        sw.AppendLine("-1");
                    }
                    else
                    {
                        sw.Append(queue.Last() + "\n");
                    }
                }
            }
            Console.WriteLine(sw.ToString());
        }
    }
}