요세푸스 문제 0

문제

요세푸스 문제 0

풀이

먼저 큐에 부터 까지 차례대로 넣습니다. 번째 사람을 제거하는 것은 번 큐에서 하나 뽑고 다시 넣기를 반복한 다음, 큐에서 하나를 뽑아 제거하는 것과 같습니다. 이를 큐가 빌 때 까지 반복하면 됩니다.

출력 형식이 특이함에 유의합시다.

코드

Python

import sys
from collections import deque
 
input = lambda: sys.stdin.readline().rstrip()
 
n, k = map(int, input().split())
queue = deque([i for i in range(1, n + 1)])
answerList = []
while queue:
    for i in range(k-1):
        queue.append(queue.popleft())
    answerList.append(queue.popleft())
 
print("<", end="")
print(*answerList, sep=", ", end="")
print(">")

C++

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, k;
    cin >> n >> k;
    vector<int> answerList;
    queue<int> q;
    for (int i = 1 ; i <= n ; i++) q.push(i);
    while (not q.empty()) {
        for (int i = 0 ; i < k-1 ; i++) {
            q.push(q.front());
            q.pop();
        }
        answerList.push_back(q.front());
        q.pop();
    }
    cout << '<';
    for (int i = 0 ; i < answerList.size()-1 ; i++) {
        cout << answerList[i] << ", ";
    }
    cout << answerList.back();
    cout << '>';
 
    return 0;
}

Java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        StringTokenizer tk = new StringTokenizer(br.readLine());
 
        int n = Integer.parseInt(tk.nextToken()), k = Integer.parseInt(tk.nextToken());
 
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++)
            queue.add(i);
 
        ArrayList<Integer> answerList = new ArrayList<>();
        while (!queue.isEmpty()) {
            for (int i = 0; i < k - 1; i++)
                queue.add(queue.poll());
            answerList.add(queue.poll());
        }
 
        bw.write('<');
        for (int i = 0; i < n - 1; i++)
            bw.write(answerList.get(i) + ", ");
        bw.write(answerList.get(n - 1) + ">");
 
        bw.close();
    }
}