[C#] 백준 24511번 queuestack

[ 문제 ]

한가롭게 방학에 놀고 있던 도현이는 갑자기 재밌는 자료구조를 생각해냈다. 그 자료구조의 이름은 queuestack이다.

queuestack의 구조는 다음과 같다. 1번, 2번, ... , N번의 자료구조(queue 혹은 stack)가 나열되어있으며, 각각의 자료구조에는 한 개의 원소가 들어있다.

queuestack의 작동은 다음과 같다.

•  x_0을 입력받는다.
•  x_0을 1번 자료구조에 삽입한 뒤 1번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 x_1이라 한다.
•  x_1을 2번 자료구조에 삽입한 뒤 2번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 x_2이라 한다.
• ...
•  x_{N-1}을 N번 자료구조에 삽입한 뒤 N번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 x_N이라 한다.
•  x_N을 리턴한다.

도현이는 길이 M의 수열 C를 가져와서 수열의 원소를 앞에서부터 차례대로 queuestack에 삽입할 것이다. 이전에 삽입한 결과는 남아 있다. (예제 1 참고)

queuestack에 넣을 원소들이 주어졌을 때, 해당 원소를 넣은 리턴값을 출력하는 프로그램을 작성해보자.

 

[ 코드 ]

1. 내 코드

using System.Text;

StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
StreamWriter sw = new StreamWriter(new BufferedStream(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>();

if(a.All(x=> x == 1))
{
    sb.Append(string.Join(" ", c));
}
else
{
    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 first = list.Last.Value;
        list.RemoveLast();
        sb.Append($"{first} ");
    }
}

sw.Write( sb.ToString().TrimEnd() );
sw.Flush();
sw.Close();
sr.Close();

 

2. 다른 사람 코드

using System;
using System.IO;
using System.Text;
using System.Collections.Generic;
using System.Linq;
class main {
    static StreamReader rd = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
    static StreamWriter wr = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
    static StringBuilder std = new StringBuilder();
  static void Main(){
      int n = int.Parse(rd.ReadLine());
      int[] stq = Array.ConvertAll(rd.ReadLine().Split(), int.Parse);
      int[] arr = Array.ConvertAll(rd.ReadLine().Split(), int.Parse);
      
      int d = int.Parse(rd.ReadLine());
      int[] data = Array.ConvertAll(rd.ReadLine().Split(), int.Parse); 
      
      deq de = new deq(n+d);
      for(int i = n-1; i >= 0; i--)
      {
          if(stq[i] == 0)
          {
              de.frontPush(arr[i]);
          }
      }
      
      for(int i = 0; i < d; i++)
      {
          de.frontPush(data[i]);
          std.Append(de.backPop() + " ");
      }
      
      wr.Write(std);
      wr.Close();
  }
}
class deq
{
    int[] arr;
    int left;
    int right;
    public deq(int n)
    {
        arr = new int[n * 2];
        left = n;
        right = n+1;
    }
    public void frontPush(int n)
    {
        arr[left] = n;
        left--;
    }
    public void backPush(int n)
    {
        arr[right] = n;
        right++;
    }
    public int frontPop()
    {
        if(right - left == 1)
        {
            return -1;
        }
        left++;
        return arr[left];
    }
    public int backPop()
    {
        if(right - left == 1)
        {
            return -1;
        }
        right--;
        return arr[right];
    }
    public int size()
    {
        return right - left - 1;
    }
    public int enpty()
    {
        return right - left == 1 ? 1 : 0;
    }
    public int frontPeek()
    {
        if(right - left == 1)
        {
            return -1;
        }
        return arr[left+1];
    }
    public int backPeek()
    {
        if(right - left == 1)
        {
            return -1;
        }
        return arr[right-1];
    }
}

- 시간복잡도를 O(n)으로 해야합니다........

 

[ 실행화면 ]

case: 1

 

 

 

 

 

---

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

24511번: queuestack