[백준 - C#] 1158번 요세푸스 문제

문제링크

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

1158번: 요세푸스 문제

 

문제

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

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

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

조건

시간제한 : 2초
메모리 제한 : 256 MB

입력

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

출력

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

 

문제정리

1. 1번부터 N번까지 사람이 원으로 있을 때 K번째 사람을 제거해야합니다.
2. K번째 사람이 제거되면 남은 사람을 계속해서 같은 방식으로 제거합니다. 

이번 문제의 경우 1번 부터 N번까지 사람이 원으로 앉아있을 때 K번째 사람을 반복해서 제거하며 제거된 순서를 순열로 표기하는 문제입니다.

이 문제는 Queue로 풀 수 있으며 큐에 1번 부터 N번까지 값을 넣고 K-1번째 사람까지 계속 pop하고 다시 push하면 맨 앞에 제거되야될 사람만 남게 됩니다.

예를들어 

N이 7이고 k가 3일때
queue => 1 2 3 4 5 6 7
POP, PUSH => 2 3 4 5 6 7 1 
POP, PUSH => 3 4 5 6 7 1 2
K번째 사람 POP = 4 5 6 7 1 2  (3은 출력) 

위와 같이 반복하게 되면 결국 큐는 1개만 남게되고 한번더 디큐하여 출력하게되면 수열을 찾을 수 있습니다.

 

C# 코드

static void Main(string[] args)
{
    StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
    StreamReader reader = new StreamReader(Console.OpenStandardInput());
 
    string[] input = reader.ReadLine().Split();
    int N = int.Parse(input[0]);
    int K = int.Parse(input[1]);
 
    Queue<int> queue = new Queue<int>();
 
    // 1부터 N까지를 큐에 담습니다.
    for (int i = 1; i <= N; i++)
        queue.Enqueue(i);
 
    writer.Write("<");
 
    while (queue.Count > 1)
    {
        // K-1번까지 큐에서 디큐하고 다시 인큐 합니다
        for (int i = 1; i < K; i++)
            queue.Enqueue(queue.Dequeue());
 
        // 제거해야될 K번째 사람을 디큐해주고 출력해줍니다.
        writer.Write($"{queue.Dequeue()}, ");
    }
 
    writer.WriteLine($"{queue.Dequeue()}>");
 
    writer.Close();
    reader.Close();
}

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.