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

1. 문제

1158번: 요세푸스 문제

2. 개요

1번부터 N번까지의 사람이 원을 그리며 앉아있다.

순서대로 K번째 사람을 제거하고 남은 사람들로 다시 원을 구성한다.

남은 사람이 없어질 때 까지 이 작업을 반복한다.

이 때 원에서 제거되는 사람들의 순열을 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

앞에서 K-1까지는 앞에서 빼낸 이후 다시 뒤로 넣어준다.

K번째 사람은 빼내면서 다시 뒤로 넣지 않으며 답을 갱신한다.

이를 리스트나 큐가 빌 때까지 반복한다.

모든 작업이 완료되면 답을 출력한다.

3-2. Python

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())

q = deque([i+1 for i in range(N)])
answer = "<"

while len(q) > 1:
    q.rotate(-(K-1))
    answer += "%s, " %q.popleft()

answer += "%s>" %q.popleft()
print(answer)

3-3. C#

namespace boj_1158
{
    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(Enumerable.Range(1, N));
            string answer = "<";

            while (q.Count > 1)
            {
                for (int i = 0; i < K - 1; i++)
                    q.Enqueue(q.Dequeue());

                answer += $"{q.Dequeue()}, ";
            }

            answer += $"{q.Dequeue()}>";
            Console.WriteLine(answer);
        }
    }
}