C#) [BOJ] 1158 요세푸스 문제

1158번: 요세푸스 문제 (acmicpc.net)

 

 

 

 

원형 큐 구현 로직에 해당 문제를 대입하여 문제를 해결한 경우

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace _230218
{
    class Program
    {
        public static int[] arr;
        public static int front;
        public static int rear;
        public static int idx;

        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int[] nk = Array.ConvertAll(sr.ReadLine().Split(' '), int.Parse);
            int n = nk[0];
            int k = nk[1];

            arr = new int[n + 1];

            front = -1;
            rear = -1;
            int cnt = 0;

            for(int i = 1; i <= n; i++)
            {
                Enqueue(i);
            }

            List<int> ansList = new List<int>();

            while (true)
            {
                int num = Dequeue();
                cnt++;                
                if(cnt == k)
                {
                    ansList.Add(num);
                }
                else
                {
                    Enqueue(num);
                }

                if (cnt == k) cnt = 0;
                if (front == -1 && rear == -1) break;
            }

            sw.Write("<");
            for (int i = 0; i < ansList.Count; i++)
            {
                if (i == ansList.Count - 1) sw.Write(ansList[i]);
                else sw.Write("{0}, ", ansList[i]);
            }
            sw.WriteLine(">");

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

        public static void Enqueue(int item)
        {
            if ((rear + 1) % arr.Length == front) throw new ApplicationException("Full.");
            else
            {                
                if (front == -1) front++;

                rear = (rear + 1) % arr.Length; 
                arr[rear] = item;
            }
        }

        public static int Dequeue()
        {
            if (front == -1 && rear == -1) throw new ApplicationException("Empty");
            else
            {
                int data = arr[front];

                if (front == rear)
                {
                    front = -1;
                    rear = -1;
                }
                else front = (front + 1) % arr.Length;

                return data;
            }            
        }
    }
}

 

 

 

실제 Queue를 사용하여 코드의 길이를 줄여 사용한 경우

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace _230218_2
{
    class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int[] nk = Array.ConvertAll(sr.ReadLine().Split(' '), int.Parse);
            int n = nk[0];
            int k = nk[1];

            Queue<int> q = new Queue<int>();

            for(int i = 1; i <= n; i++)
            {
                q.Enqueue(i);
            }

            sw.Write("<");
            while(q.Count > 1)
            {
                for(int i = 1; i < k; i++)
                {
                    int tmp = q.Peek();
                    q.Dequeue();
                    q.Enqueue(tmp);
                }

                sw.Write("{0}, ", q.Peek());
                q.Dequeue();
            }
            sw.Write("{0}>", q.Peek());

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

        }
    }
}

 

  while문을 q의 요소가 1개가 남을 때까지 반복하면서 내부의 for문을 k만큼 반복하여 나온 수를 출력하고 Dequeue하는 식으로 반복한 후 마지막 요소의 값을 문제의 출력 형식에 맞게 출력하면 된다. 기본적으로 C#의 컬렉션은 동적 배열이기 때문에 선입선출 방식 단점이 적용되지 않는다.