기초 알고리즘 - 요세푸스 문제

1 2 3 4 5 6 7 -> 3
1 2 4 5 6 7 -> 6
1 2 4 5 7 -> 2
1 4 5 7 -> 7
1 4 5 -> 5
1 4 -> 1
4
이 순열은 N, K를 입력받아 N까지의 수에서 K번쨰 수를 제거해가는 순열이다. K번째 수를 제거하면, K+1부터 3번째 수를 제거한다. 이 때, 원탁에 앉아있으므로, 앞선 문자들이 전부 다시 뒷열에 넣어줘야한다.

즉, K-1까지 빼서, 리스트에 넣어주고 K는 반환해 따로 result 배열에 넣어준다. queue를 이용하면 과정이 쉬워진다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Hello_world {
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Queue<Integer> queue = new LinkedList<>();
		 
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		int[] result = new int[N]; //결과값을 넣어줄 배열
		//queue에 1~N까지 넣어줌
		sb.append("<");
		
		for(int i =0; i<N-1; i++) {
			queue.add(i+1);
		}
		
		
		while(queue.size()>1){
			
		for(int i=0; i<K-1; i++) {
			queue.add(queue.poll());
		}
		sb.append(queue.poll()).append(", ");
		}
		
		
		sb.append(queue.poll()).append('>');
		System.out.println(sb);
	}
}