[158]ジョセフス問題|白駿銀色4

12628 ワード
キュー パイ ジャワ stream python 白駿 queue テキストリンク

🔎 問題の説明


質問リンク
ジョセフス問題は以下の通りです.
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 ≤ 5,000)

    • 🧪 JAvaコード

    import java.io.*;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Josephus {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //(1 ≤ K ≤ N ≤ 5,000)
        String[] cmd = br.readLine().split(" ");
        int N = Integer.parseInt(cmd[0]);
        int K = Integer.parseInt(cmd[1]);
				
		//1부터N까지 들어있는 리스트 생성 //boxed : int -> integer
        List<Integer> Q =  IntStream.range(1,N+1).boxed().collect(Collectors.toList());

        for (int i = -1; 0 < N; i--) {//i = Q의 index번호라 1씩 빼줌
            Q.add(Q.remove(i = (i + K) % N--));
        }
		//리스트에 구분자 ", "넣고 스트링으로 반환
        bw.write("<"+Q.stream().map(String::valueOf).collect(Collectors.joining(", "))+">");
        bw.flush();
        bw.close();
    }
}
    Streamで解いたStreamとStringBuilderを使用しないメモリ/時間効率は同等です.
    でも銀4じゃないみたい銀色にしたい

    🧊 Pythonコード

    from collections import deque
N, K = map(int, input().split())  # (1 ≤ K ≤ N ≤ 5,000)
Q, res = deque([*range(N)]), []   # Q = [0...N-1] , res = []
while Q:
    Q.rotate(-K+1) # Q회전
    res.append(Q.popleft()+1) #Q맨앞요소 res로 push
print('<'+str(res)[1:-1]+'>')
    Pythonはrotate()を考慮して論理を容易に思いついた.
    現在のノードの下の1番目の要素のテキスト内容を取得
    [BOJ]11052購入カード