白駿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つのケース(たとえば
  • を削除するかどうか)がある場合は、ブール配列を使用するか特殊文字(null,0などの初期化値)を使用するかを考慮します(
  • ).
  • の出力値の位置に応じて、スタック、キューなどのデータ構造を使用すると便利です.
  • 質問リンク:
    https://www.acmicpc.net/problem/11866