백준 11866 java 요세푸스 문제0 풀이

1. 문제 분석

1. 1번부터 N번까지 N명의 사람이 원을 이루고 앉아있다
: 특정 배열 또는 리스트의 처음과 끝이 연결되어 있다는 것이고 출제자의 의도는 큐였다.
하지만 본인은 큐를 아직 배우지 않았기 때문에 알고 있는 구현 방법에 한해서 풀고자 했다.

2. 양의 정수 K만큼 자리를 확인하며 사람을 제거한다.
: 이미 제거된 사람인지의 여부를 확인할 식별자가 필요함(boolean 배열을 따로 만들거나 기존의 배열에서 특수 문자(0[N 양의 정수) 또는 절대 간섭을 받지 않을 문자)로 처리 - 본인 코드는 기존 배열의 수를 0으로 할당하여 구현하였다.

3. 사람이 제거되는 순서 대로 출력하라.
: 제거된 사람을 담는 배열이 필요해 보인다.

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. 소스코드

참고사항
큐가 아닌 재귀로 해결한 케이스이다. (전날 알고리즘의 왕님의
재귀 강의가 있었기 때문에 더더욱 재귀를 쓰고 싶었ㄷ...)

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. 숙지할 내용

1. 배열의 인덱스 초과 여부는 %(모듈러)를 통해 확인 가능함
2. 탐색과 같은 중복된 동작에 대해서는 재귀를 통해 코드 반복 제거
3. 제거 여부와 같은 2가지 경우를 조건으로 갖는 경우 boolean형 배열을 활용할 지 아니면 특수 문자로 처리할지(null, 0과 같은 초기화 값) 고려
4. 출력할 값의 위치에 따라 stack, queue와 같은 자료구조를 활용하면 더욱 편함.

문제 링크:
https://www.acmicpc.net/problem/11866