백준 11866번: 요세푸스 문제 0

요세푸스 문제는 N명의 사람이 동그랗게 둘러 앉아있을 때,

원을 따라 모든 사람을 제거할 때 까지 순서대로 K번째 사람을 제거하는 문제이다.

예를 들어 N = 7, K = 3이라고 하면,

1, 2, 3, 4, 5, 6, 7의 사람이 원을 그리며 둘러 앉아있는 것이다.

1. 3번 째 사람(1, 2, 3)인 3번을 제거한다.
2. 그 뒤로 3칸 이동해서(4, 5, 6) 6번을 제거한다.
3. 그 뒤로 3칸 이동해서(7, 1, 2) 2번을 제거한다.
4. 그 뒤로 3칸 이동해서(4, 5, 7) 7번을 제거한다.
5. 이런 식으로 진행해서 모든 사람을 제거한다.
6. 그 결과로 N = 7, K = 3일 때 답은 3, 6, 2, 7, 5, 1, 4이다.

우선, 문제를 풀면서 배열을 사용한다고 했을 때,

요소를 제거하고 배열의 길이를 조절하는 과정이 힘들 거라는 생각이 들었다.

그래서 요소를 추가•제거할 때 동적으로 배열의 길이를 조절해주는 ArrayList를 사용하기로 했다.

또한, 새로운 ArrayList를 만들어서 거기에 순서대로 뽑아낸 요소들을 저장해주었다.

마지막으로 문제에서 제시한 출력 형식에 맞추어 출력해주었다.

이때, '\b'가 백스페이스여서 이걸로 써서 출력형식을 맞춰보려고 했으나,

'\b'를 출력하는 것이 기존 출력을 지우는 것이 아닌 그저 지운 것 처럼 보이게 할 뿐이어서 한 번 틀리고,

'\b'를 쓰지 않고 출력 형식을 맞추도록 수정을 해주었다.

 

아래는 그렇게 하여 문제를 푼 코드이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.ArrayList;


public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		ArrayList<Integer> aList = new ArrayList<>();
		for(int i = 0; i < N; i++) aList.add(i + 1);
		br.close();

		int idx = K - 1;
		ArrayList<Integer> res = new ArrayList<>();
		while (N != 0) {
			res.add(aList.remove(idx));
			if (--N == 0) break;
			idx = (idx + K - 1)%N;
		}

		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		bw.write("<");
		N = res.size();
		for (int i = 0; i < N - 1; i++) bw.write(res.get(i) + ", ");
		bw.write(res.get(N - 1) + ">"); 
		bw.flush();
		bw.close();
	}
}