C# 1158 요세푸스 문제

그냥 큐를 이용해서 푼 코드

using System;
using System.Collections;

namespace _1158
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] nk = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            int n = nk[0];
            int k = nk[1];

            Queue q = new Queue();
            int[] JosephusArr = new int[n];

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

            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < k-1; j++)
                {
                    int num = (int)q.Dequeue();
                    q.Enqueue(num);
                }
                int JosephusNum = (int)q.Dequeue();                                
                JosephusArr[i] = JosephusNum;

                //q 값 확인
                //Console.Write("\nq value:");
                //foreach (var num in q)
                //{
                //    Console.Write(num);
                //}
                //Console.WriteLine();
            }

            Console.Write("<");
            for (int i = 0; i < n-1; i++)
            {               
                Console.Write("{0}, ",JosephusArr[i]);
            }
            Console.Write("{0}>", JosephusArr[JosephusArr.Length - 1]);
        }
    }
}

 

위의 코드를 바탕으로

배열을 사용한 원형 큐를 구현해 푼 코드

using System;
using System.Collections;

namespace _1158
{
    class Program
    {
        //원형 큐 클래스
        class CircularQueue
        {
            public int front = 0;
            public int rear = 0;
            public int size;
            public int[] arrQ;

            public CircularQueue(int size)
            {

                this.size = size;
                this.arrQ = new int[this.size];
            }

            public void Enqueue(int num)
            {
                if ((this.rear + 1) % this.size == this.front)
                {
                    //큐 가득 참
                }
                else
                {
                    this.rear = (this.rear + 1) % this.size;
                    this.arrQ[this.rear] = num;
                    //Console.WriteLine("rear: {0}, add arrQ value: {1}", this.rear, this.arrQ[this.rear]);
                }
            }
            public int Dequeue()
            {
                if (this.rear == this.front)
                {
                    //큐 비어있음
                    return -1;
                }
                else
                {
                    this.front = (this.front + 1) % this.size;
                    //Console.WriteLine("front: {0}",front);
                    int temp = arrQ[front];
                    arrQ[front] = 0;
                    return temp;
                }
            }
        }

        static void Main(string[] args)
        {
            int[] nk = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            int n = nk[0];
            int k = nk[1];

            CircularQueue circularQueue = new CircularQueue(n+1);
            int[] JosephusArr = new int[n];

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

            //circularQueue.arrQ의 k번째 값을 JosephusArr에 넣는 과정을 반복한다
            for (int i = 0; i < n; i++)
            {
                //circularQueue.arrQ의 1~k-1 번째 값을 Dequeue한 후
                //circularQueue.arrQ에 Enqueue한다
                for (int j = 0; j < k - 1; j++)
                {                   
                    int num = circularQueue.Dequeue();
                    circularQueue.Enqueue(num);
                }

                int JosephusNum = circularQueue.Dequeue();
                JosephusArr[i] = JosephusNum;
            }

            Console.Write("<");
            for (int i = 0; i < n - 1; i++)
            {
                Console.Write("{0}, ", JosephusArr[i]);
            }
            Console.Write("{0}>", JosephusArr[JosephusArr.Length - 1]);           
        }
    }
}

 

결과