[C#] 28279번: 덱 2

목차

---

백준 단계별로 풀어보기

25.11.23

16단계: 스택, 큐, 덱 1

28279번: 덱 2

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

 

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

>> Deque (덱)

: 모든 요소에 대한 빠른 임의 액세스와 앞, 뒤쪽 모두 효율적인 삽입 및 삭제가 가능한 자료구조이다.

--> 하지만 C#에서 Deque 자료구조를 지원하지 않는다.

 

※ 공식 문서 - Deque (C++)

deque 클래스

 

>> LinkedList

: 이중으로 연결된 List로, 각 요소가 노드(Node)로 구성되며 각 노드는 데이터와 다음 노드에 대한 참조, 이전 노드에 대한 참조를 포함한다.

• 동적 메모리 할당을 통해 크기가 가변적이다.
• 연속적인 메모리 주소에 저장되는 것이 아니라 비연속적으로 저장되며, 이전과 다음 노드 정보를 통해 데이터를 연결한다.
• 배열과 달리 요소의 삽입 및 삭제가 용이하다.

 

>> 주요 메서드

• AddFirst(x) : 주어진 요소 x를 LinkedList의 시작 부분에 새로운 노드로 추가한다.
• AddLast(x) : 주어진 요소 x를 LinkedList의 끝 부분에 새로운 노드로 추가한다.
• Remove(x) : 주어진 요소 x와 첫 번째로 일치하는 요소를 LinkedList에서 제거한다.
• RemoveFirst() : LinkedList의 첫 번째 노드를 제거한다.
• RemoveLast() : LinkedList의 마지막 노드를 제거한다.
• First : LinkedList의 첫 번째 노드를 가져온다. 노드가 없는 경우 null을 반환한다.
• Last : LinkedList의 마지막 노드를 가져온다. 노드가 없는 경우 null을 반환한다.
• Count : LinkedList에 있는 요소의 개수를 반환한다.
• Clear() : LinkedList에 있는 모든 요소를 제거한다.

 

 

※ 공식 문서 - LinkedList

LinkedList<T> 클래스 (System.Collections.Generic)

 

문제 풀이

: 원래는 Deque을 활용하여 푸는 문제지만, C#에서 Deque를 지원하지 않기 때문에 LinkedList를 활용하여 구현하자.

1. StreamReader로 입력값을 받아 int값으로 변환하여 명령의 수를 담을 변수 n 에 담고, int형 LinkedList list 를 초기화한다.
2. for 반복문을 통해 명령을 수행한다.
   •     StreamReader로 명령을 받아 string형 변수 input 에 담는다.
   •     switch 문을 통해 input 의 첫번째 값에 따라 명령을 수행한다.
   •     input 이 1이라면 Substring을 통해 LinkedList에 담을 정수를 변수 num1 에 담고 AddFirst로 시작 부분에 새로운 노드로 추가한다.
   •     input 이 2라면 Substring을 통해 LinkedList에 담을 정수를 변수 num2 에 담고 AddLast로 끝 부분에 새로운 노드로 추가한다.
   •     input 이 3이라면 삼항연산자를 통해 LinkedList가 비어있지 않으면 첫 번째 노드를 가져와 StringBuilder에 담고 비어있다면 -1 을 담는다. 이때, StringBuilder에 첫 번째 노드를 담았다면 RemoveFirst() 로 첫 번째 노드를 제거한다.
   •     input 이 4라면 삼항연산자를 통해 LinkedList가 비어있지 않으면 마지막 노드를 가져와 StringBuilder에 담고 비어있다면 -1 을 담는다. 이때, StringBuilder에 마지막 노드를 담았다면 RemoveLast() 로 마지막 노드를 제거한다.
   •     input 이 5라면 StringBuilder에 LinkedList의 Count를 담는다.
   •     input 이 6이라면 삼항연산자를 통해 LinkedList가 비어있지 않으면 0을, 비어있다면 1을 담는다.
   •     input 이 7이라면 삼항연산자를 통해 LinkedList가 비어있지 않으면 첫 번째 노드를 가져와 StringBuilder에 담고 비어있다면 -1 을 담는다.
   •     input 이 8이라면 삼항연산자를 통해 LinkedList가 비어있지 않으면 마지막 노드를 가져와 StringBuilder에 담고 비어있다면 -1 을 담는다.
3. 반복문이 끝나면 StreamWriter로 StringBuilder에 담은 값을 출력한다.

 

정답 코드

using System.IO;
using System.Text;

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

        int n = int.Parse(sr.ReadLine());
        LinkedList<int> list = new LinkedList<int>();

        for (int i = 0; i < n; i++)
        {
            string input = sr.ReadLine();

            switch (input[0])
            {
                case '1':
                    int num1 = int.Parse(input.Substring(2));
                    list.AddFirst(num1);
                    break;
                case '2':
                    int num2 = int.Parse(input.Substring(2));
                    list.AddLast(num2);
                    break;
                case '3':
                    sb.AppendLine(list.Count > 0 ? list.First.Value.ToString() : "-1");
                    if (list.Count > 0)
                        list.RemoveFirst();
                    break;
                case '4':
                    sb.AppendLine(list.Count > 0 ? list.Last.Value.ToString() : "-1");
                    if (list.Count > 0)
                        list.RemoveLast();
                    break;
                case '5':
                    sb.AppendLine(list.Count.ToString());
                    break;
                case '6':
                    sb.AppendLine(list.Count > 0 ? "0" : "1");
                    break;
                case '7':
                    sb.AppendLine(list.Count > 0 ? list.First.Value.ToString() : "-1");
                    break;
                case '8':
                    sb.AppendLine(list.Count > 0 ? list.Last.Value.ToString() : "-1");
                    break;
            }
        }
        sw.Write(sb.ToString());
    }
}