白駿11866 javaジョセフ問題0解答
1.問題分析
1.1番からN番まで、N人が丸になって座っている
:特定の配列またはリストの先頭と末尾が接続されており,出題者の意図はキューである.
しかし、私はまだQを勉強していないので、知っている実現方法に限られています.
2.正数Kの位置を確認し、人を取り除く.
:削除されたかどうかを判断する識別子(ブール配列を作成するか、既存の配列で特殊文字(0[n個の整数)または絶対干渉されない文字を使用するか)が必要です.コードは、既存の配列の数を0に指定することで実現されます.
削除者順に印刷します.
:削除された者を含む配列が必要になります.
4.(*)サンプル出力は、A B Cではなく、「<」、「,」、「>」などの特殊な場合である.私はこの部分でFailが出てきました
2.テストケーススタディ
例1)1 2 3 4 5座って、Kが2であれば、
削除2、削除4、削除1、削除3、削除5(削除者が重複しない)
例2)1 2 3 4 5座って、Kが3であれば、
削除3、削除1、削除5、削除2、削除4(3番目の削除者から)
3.ソースコード
注意事項
Qではなく回帰で解決する場合(前日アルゴリズムの王の
回帰講座があるので、もっと回帰を使いたい…)
import java.util.Scanner;
public class Boj_11866 {
private static int N;
private static int K;
private static int index;
private static int[] nums;
private static int[] answer;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
K = sc.nextInt();
nums = new int[N];
answer = new int[N];
for (int i = 0; i < nums.length; i++) { // 1~N으로 배열 초기화
nums[i] = i+1;
}
for(int i = 0; i < N; i++) { // 숫자 N개 전부 확인
for (int j = 0; j < K; j++) { // K번 만큼 이동하여 제거할 사람 탐색
index = move(index); // 제거하지 않은 사람 탐색하여 1만큼 이동.
}
// 배열의 인덱스의 경우 N-1까지 존재index가 0인 경우 N번째 사람에 해당함
if (index == 0) {
answer[i] = N;
} else {
answer[i] = index; // 제거한 사람 출력할 순서대로 담아두기
}
nums[index] = 0; // 제거 표시
}
// 출력
System.out.print("<");
for (int i = 0; i < N; i++) {
if (i == N-1) {
System.out.print(answer[i]+">");
} else {
System.out.print(answer[i] + ", ");
}
}
}
public static int move(int index) {
int tmpIndex = (index+1) % N;
if(nums[tmpIndex] != 0) { //1 이동 시 기확인 여부
return tmpIndex;
} else { // 확인하지 않은 곳 탐색
return move(tmpIndex);
}
}
}
4.おなじみの内容
2つのケース(たとえば
https://www.acmicpc.net/problem/11866
Reference
この問題について(白駿11866 javaジョセフ問題0解答), 我々は、より多くの情報をここで見つけました https://velog.io/@chaaany/java-백준-11866-요세푸스-문제0テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol