[伯俊]BOJ 11866ヨセフ問題0 JAVA

BOJ 11866ジョセフス問題0

質問する

ジョセフス問題は以下の通りです.
1番からN番までは、N人が1つの円に座り、正の整数K(≦N)を与えます.今は順番にK人目を除いています.一人が取り除かれると、残りの人からなる円に沿ってこの過程が続きます.この過程はN人全員がクリアされるまで続く.円上の人々が消去される順序を(N,K)−ジョセフス配列と呼ぶ.例えば、(7,3)−ジョセフス配列<3,6,2,7,5,1,4>である.
NとKをあげると(N,K)-ジョセフスシーケンスを求めるプログラムを書きます.

入力

第1行NとKは、スペースを隔てて順次与えられる.(1 ≤ K ≤ N ≤ 1,000)

しゅつりょく

例に示すように、ジョセフスシーケンスを出力します.

サンプルI/O

入力:7 3

出力:<3, 6, 2, 7, 5, 1, 4>

ソースコード

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        int n = sc.nextInt();
        int k = sc.nextInt();

        Queue<Integer> q = new LinkedList<>();

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

        sb.append("<");
        while (q.size() != 1) {
            for (int i = 1; i <= k - 1; i++) {
                q.add(q.poll());
            }

            sb.append(q.poll()).append(", ");
        }

        sb.append(q.poll()).append(">");

        System.out.println(sb.toString());
    }
}

Comment

キューが最も基本的な問題

キュー構造に関する質問:BOJ 18258