[C#] 백준 1158 알고리즘

https://www.acmicpc.net/problem/1158

문제

 

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

출력

 

예제와 같이 요세푸스 순열을 출력한다.

예제 입력

7 3

예제 출력

<3, 6, 2, 7, 5, 1, 4>

 

 

 

문제 풀이

 

Queue를 이용해 수를 빼고 다시 넣는 방식으로 하나 하나 제거하게끔 풀이를 하였다.

 

모든 수를 다 빼야하기 때문에 Queue의 count가 0 이 될 때 까지 반복을 하며, K번째 수를 제외하게 되면 count를 초기화해야 되는 점이 중요점이다.

 

정답

using System.Text;

namespace CodeTest
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int N = int.Parse(input[0]);
            int K = int.Parse(input[1]); 

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

            StringBuilder sb = new StringBuilder();
            sb.Append("<");

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

            while (q.Count != 0)
            {
                count++;
                if (count == K)
                {
                    if(q.Count == 1)
                    {
                        sb.Append(q.Dequeue());
                    }
                    else
                    {
                        sb.Append(q.Dequeue() + ", ");
                    }
                   count = 0;
                }
                else
                {
                    q.Enqueue(q.Dequeue());
                }
                
            }

            sb.Append(">");
            Console.WriteLine(sb.ToString());
        }
    }
}

 

처음에 count를 증가시켜주면서 K와 같을 때 q를 dequeue해주며 초기화시켜준다. 마지막 쉼표는 빠져야 하기 때문에 if문으로 조건을 줬다.

 

else의 q.Enqueue(q.Dequeue()); 부분은 처음에 queue를 하나 더 만들어서 이쪽으로 옮겨줄까 하다가 빼면서 다시 enqueue하면 되지 않을까 하여 동작을 해보니 되었다.

 

 

동작하면 이런식으로 동작이 된다.

 

 

회고

이전에 apend나 console.Write() 당시에 dequeue를 하면 바로 빠지는 걸 생각해서 enqueue와 동시에 동작을 해보니 되었던 점이 좋았으며, 노가다 식으로 안될 때 마다 수정하면서 풀어서 해결했던 점이 도움이 되었다.