백준 1168 (요세푸스 2)

문제

---

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

 

 

 

 

 

풀이

---

세그먼트트리를 이용한 문제를 이해하는데 오래걸렸다.

 

1 ~ n 까지중 아직 제거되지 않은 수를 1로 두고 제거된 수를 0으로 둔 뒤

그 수들의 구간합을 세그먼트 트리로 구현한 트리를 이용해 문제를 푼다.

 

아래의 반복문을 통해 풀 수 있다.

 

for(int i = 0 ; i < n ; i++) {
			
	int size = n - i;
	index += k - 1;
			
	if(index % size == 0) {
		index = size;
	}
	else if(index > size) {
		index %= size;
	}
			
	int num = query(1, n, 1, index);
	update(1, n, 1, num);
			
	if(i == n - 1)
		sb.append(num + ">");
	else
		sb.append(num +", ");
}

여기서 k가 아닌 k - 1 을 더해주는 이유는 한번씩 반복문이 질행 될때 마다 하나씩 size 의 크기가 줄게 된다.

그 말의 의미는 현재의 수가 빠진 뒤에서 k 번째 라는 것은 수 적으로 생각하면 k-1 번째 수가 된다.

예를들면

7 3 의 예시에서

<1 2 3 4 5 6 7> 까지의 숫자중

      ↑

3 이 먼저 선택이 되면 남는 수는 

<1 2 4 5 6 7> 이 된다.

      ↑

3이 이미 제거가 됐으니 현재의 화살표는 4방향에 있다고 생각을 하고 문제를 풀면된다.

 

따라서 k - 1 만큼 더 진행을 하면 된다.

 

쿼리 함수는 다음과 같다.

public static int query(int start, int end, int node, int val) {
	
	if(start == end)
		return start;
	int mid = (start + end) / 2;
	
	if(val <= tree[2 * node])
		return query(start, mid, 2 * node, val);
	else
		return query(mid + 1, end, 2 * node + 1, val - tree[2 * node]);
}

앞으로 나아갈 방향을 정하는 쿼리 함수다.

현재 있는 곳의 왼쪽 자식 노드의 구간합보다 현재의 수가 크면 오른쪽 노드 구간에 있게 된다.

하지만 아니라면 왼쪽 노드구간에 있다는 것이므로 재귀적으로 진행을 하면된다.

 

오른쪽 노드 구간에 있다면 구간합을 빼주어 맞는 위치를 찾아가게 한다.

 

나머지 함수들은 다른 일반적인 세그먼트 트리와 비슷하기 때문에 따로 설명하지 않겠다.

<전체 코드>

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

public class Main {	
	
	static StringBuilder sb = new StringBuilder();
	static int[] tree;

	public static void main(String[] args) throws IOException{
		
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
			
		tree = new int[400040];
		init(1, n, 1);
		
		int index = 1;
		
		sb.append("<");
		for(int i = 0 ; i < n ; i++) {
			
			int size = n - i;
			index += k;
			
			if(index % size == 0) {
				index = size;
			}
			else if(index > size) {
				index %= size;
			}
			
			int num = query(1, n, 1, index);
			update(1, n, 1, num);
			
			if(i == n - 1)
				sb.append(num + ">");
			else
				sb.append(num +", ");
		}
		
		
		System.out.println(sb);
	}
	
	public static int init(int start, int end, int node) {
		if(start == end) {
			return tree[node] = 1;
		}
		
		int mid = (start + end) / 2;
		
		return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
	}
	
	public static int query(int start, int end, int node, int val) {
		
		if(start == end)
			return start;
		
		int mid = (start + end) / 2;
		
		if(val <= tree[2 * node])
			return query(start, mid, 2 * node, val);
		else
			return query(mid + 1, end, 2 * node + 1, val - tree[2 * node]);
	}
	
	public static long update(int start, int end, int node, int a) {
		
		if(start == end) {
			return tree[node] = 0;
		}
		
		tree[node]--;
		
		int mid = (start + end) / 2;
		if(a > mid) {
			return update(mid + 1, end, 2 * node + 1, a);
		}
		else {
			return update(start, mid, 2 * node, a);
		}
		
	}
}