[C#] 24511번: queuestack

목차

---

백준 단계별로 풀어보기

25.11.25

16단계: 스택, 큐, 덱 1

24511번: queuestack

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

 

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

>> Select

: LINQ에서 지원하는 함수로, 컬렉션의 각 요소를 다른 형태로 바꾸는 작업을 수행한다.

--> 실제로 값을 바로 변환하는 것이 아니라 변환 규칙만 저장해두고 나중에 foreach나 ToArray()가 호출될 때 비로소 변환한다.

 

- 기본 정의

public static IEnumerable<TResult> Select<TSource,TResult>
(this IEnumerable<TSource> source, Func<TSource,int,TResult> selector);

• 입력 : IEnumerable<TSource> - 배열, 리스트 등
• 출력 : IEnumerable<TResult> - 변환된 타입
• selector : 각 요소를 어떻게 변환할지 정의하는 함수

- 사용법

1. 숫자 입력을 파싱하는 경우

// 입력값: 1 2 3 4 에 대하여
int[] arr = Console.ReadLine().Split.Select(int.Parse).ToArray();
// 결과: arr = {1, 2, 3, 4}

 

2. 람다식을 활용

int[] nums = { 1, 2, 3, 4 };
int[] squares = nums.Select(n => n * n).ToArray();
// 결과: squares = { 1, 4, 9, 16 }

 

3. 타입 변경

string[] words = { "apple", "banana" };
int[] lengths = words.Select(w => w.Length).ToArray();
// 결과: lengths = { 5, 6 }

 

※ 공식 문서 - Enumerable.Select

Enumerable.Select 메서드 (System.Linq)

 

문제 풀이

: C#에서 Deque를 지원하지 않으므로, LinkedList를 활용하여 문제를 풀었다.

문제에서 나온 queuestack(큐스택)의 작동에서 i 번 자료구조가 stack이라면, 원소를 자료구조에 삽입한 뒤 다시 pop 해도 동일한 원소가 pop 되므로 큐스택의 작동에 영향을 주지 않는다. 즉, i 번 자료구조가 queue일 때만 고려하면 된다.

--> 그렇다면 결국 해당 큐스택도 Queue와 같이 FIFO 구조를 따르게 된다.

1. StreamReader로 모든 입력값을 받아 각 상황에 맞게 Select를 활용하여 int값으로 변환하고, 각각 자료구조의 개수를 담을 변수 n, 수열 A를 담을 변수 a, 수열 B를 담을 변수 b, 삽입할 수열의 길이를 담을 변수 m, 수열 c를 담을 변수 c 에 담는다.
2. 큐스택 내부를 표현할 int형 LinkedList list 를 초기화한다.
3. for 반복문을 통해 i 번 자료구조가 queue라면 해당 원소를 list 의 마지막에 추가하여 큐스택의 초기 상태를 세팅한다.
4. for 반복문을 통해 삽입할 원소를 list 의 앞에 순서대로 추가한다.
5. for 반복문을 통해 아래 과정을 반복하여 리턴값을 StringBuilder에 담는다.
   •     list 의 마지막 요소를 리턴값을 담을 변수 result 에 담는다.
   •     list 의 마지막 요소를 제거한다.
   •     StringBuilder에 result 를 공백과 함께 담는다.
6. StreamWriter로 StringBuilder에 담은 값을 출력한다.

※ 이해를 위한 그림

: 예제 1을 시각화했다.

 

정답 코드

using System.IO;
using System.Text;
using System.Linq;

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());
        int[] a = sr.ReadLine().Split().Select(int.Parse).ToArray();
        int[] b = sr.ReadLine().Split().Select(int.Parse).ToArray();
        int m = int.Parse(sr.ReadLine());
        int[] c = sr.ReadLine().Split().Select(int.Parse).ToArray();
        
        LinkedList<int> list = new LinkedList<int>();

        for (int i = 0; i < n; i++)
        {
            if (a[i] == 0)
                list.AddLast(b[i]);
        }

        for (int i = 0; i < m; i++)
        {
            list.AddFirst(c[i]);
        }

        for (int i = 0; i < m; i++)
        {
            int result = list.Last.Value;
            list.RemoveLast();
            sb.Append(result).Append(" ");
        }
        sw.Write(sb.ToString());
    }
}

 

※ 처음 작성한 코드

: LinkedList에 Stack과 Queue 값 모두 넣고, Node를 옮겨가면서 계산했으나, 시간 제한이 1초라서 포기했다.

<hide/>
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());
        string[] a = sr.ReadLine().Split();
        string[] b = sr.ReadLine().Split();
        int m = int.Parse(sr.ReadLine());
        string[] c = sr.ReadLine().Split();
        
        LinkedList<(int queuestack, int data)> list = new LinkedList<(int, int)>();

        for (int i = 0; i < n; i++)
        {
            list.AddLast((int.Parse(a[i]), int.Parse(b[i])));
        }
        
        LinkedListNode<(int queuestack, int data)> current = list.First;
        
        for (int i = 0; i < m; i++)
        {
            int num = int.Parse(c[i]);

            for (int j = 0; j < n; j++)
            {
                if (current.Value.queuestack == 0)
                {
                    int temp = current.Value.data;
                    current.Value = (0, num);
                    num = temp;
                }
                current = current.Next ?? list.First;
            }
            sb.Append(num).Append(" ");
        }
        
        sw.Write(sb.ToString());
    }
}