백준 10845 큐 (C#)

오늘의 문제

큐 명령어를 처리하는 문제였다.
명령어는 다음과 같다.

• push X : 정수 X를 큐에 넣는다.

• pop : 큐에서 가장 앞에 있는 정수를 빼고 출력. 큐가 비어있으면 -1 출력.

• size : 큐에 들어있는 정수의 개수를 출력.

• empty : 큐가 비어있으면 1, 아니면 0 출력.

• front : 큐의 가장 앞에 있는 정수를 출력. 없으면 -1 출력.

• back : 큐의 가장 뒤에 있는 정수를 출력. 없으면 -1 출력.

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

내가 푼 방법

C#의 Queue를 사용해서 대부분의 명령어는 간단하게 처리할 수 있었다.
다만 한 가지, back 명령어는 문제가 있었다.

C#의 Queue는 맨 뒤 값을 바로 가져오는 기능이 없어서
처음엔 LINQ의 Last()를 사용했다.

queue.Last()

그런데 이렇게 하면 시간 초과가 발생할 수 있다는 걸 알게 됐다.
왜냐하면 Last()는 내부적으로 큐를 전부 순회하니까 O(n)이기 때문이다.

해결방법

push 할 때마다 들어온 값을 last라는 변수에 저장해두고
back 명령어가 들어오면 그 값을 출력하도록 했다.

int last = -1;
...
case "push":
    int num = int.Parse(input[1]);
    queue.Enqueue(num);
    last = num;
    break;
...
case "back":
    sb.AppendLine(queue.Count > 0 ? last.ToString() : "-1");
    break;

배운 점

Queue는 front 접근은 O(1) 이지만 back 접근은 직접 안 된다

이런 경우는 변수를 따로 관리해서 O(1)로 처리하는 게 정답

문제 풀 때 시간 복잡도를 항상 고려하자

최종 코드

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

namespace backjoon
{
    internal class Program
    {
        static void Main()
        {
            int count = int.Parse(Console.ReadLine());
            Queue<int> queue = new Queue<int>();
            StringBuilder sb = new StringBuilder();
            int last = -1;

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

                switch (input[0])
                {
                    case "push":
                        int num = int.Parse(input[1]);
                        queue.Enqueue(num);
                        last = num;
                        break;

                    case "pop":
                        sb.AppendLine(queue.Count > 0 ? queue.Dequeue().ToString() : "-1");
                        break;

                    case "size":
                        sb.AppendLine(queue.Count.ToString());
                        break;

                    case "empty":
                        sb.AppendLine(queue.Count > 0 ? "0" : "1");
                        break;

                    case "front":
                        sb.AppendLine(queue.Count > 0 ? queue.Peek().ToString() : "-1");
                        break;

                    case "back":
                        sb.AppendLine(queue.Count > 0 ? last.ToString() : "-1");
                        break;
                }
            }

            Console.Write(sb.ToString());
        }
    }
}