[C#] 백준 18258번 문제풀이

문제번호: 18258

문제명: 큐 2

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

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다.

 

오늘은 자료구조 문제를 풀어보았습니다.(솔브드 티어 실버 4)  이번 문제는 큐의 특성을 이용하여 명령어에 맞게 동작을 수행하는 문제였습니다. 다만, Queue는 뒤쪽 값을 출력하는 명령어를 제공하지 않기에 Last라는 LINQ를 이용해야 하는데 이 방법은 효율이 매우 좋지 않기 때문에 (시간복잡도 O(n)) 다른 자료구조를 찾아야 합니다.

이때 사용할 수 있는 것이 LinkedList입니다. LinkedList는 Queue와 거의 비슷하게 동작을 수행할 수 있으며 앞/뒤 값 접근과 갱신/삭제를 할 수 있는 자료구조입니다. 따라서 Queue를 LinkedList로 교체하니 시간초과를 피할 수 있었습니다.

다음은 정답코드입니다.

 

public static void Main()
{
    StreamReader sr = new StreamReader(Console.OpenStandardInput());
    StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

    LinkedList<int> queue = new LinkedList<int>();

    int n = int.Parse(sr.ReadLine());
    for (int i = 0; i < n; i++)
    {
        string[] inpput = sr.ReadLine().Split();
        string command = inpput[0];
        switch (command)
        {
            case "push":
                int num=int.Parse(inpput[1]);
                queue.AddLast(num);
                break;
            case "pop":
                if (queue.Count == 0)
                    sw.WriteLine(-1);
                else
                {
                    sw.WriteLine(queue.First.Value);
                    queue.RemoveFirst();
                }
                break;
            case "size":
                sw.WriteLine(queue.Count);
                break;
            case "empty":
                if (queue.Count == 0)
                    sw.WriteLine(1);
                else
                    sw.WriteLine(0);
                break;
            case "front":
                if (queue.Count == 0)
                    sw.WriteLine(-1);
                else
                    sw.WriteLine(queue.First.Value);
                break;
            case "back":
                if (queue.Count == 0)
                    sw.WriteLine(-1);
                else
                {
                    sw.WriteLine(queue.Last.Value);
                }
                break;
        }
    }

    sr.Close();
    sw.Close();
}