1168 : 요세푸스 문제 2 - JAVA

https://www.acmicpc.net/problem/1168

 

1158번의 queue를 사용한 문제와는 다르게 O(n^2)의 알고리즘을 사용하면 시간 초과가 뜬다.

 

그래서 세그먼트 트리를 사용하여 문제를 풀어야 한다.

 

나는 init으로 트리의 값들을 모두 1로 만들도록 구현했고

update는 삭제되는 배열은 0으로 만들고 안건들게 한다. 그에 맞게 업데이트를 수행하는 함수를 만들었고

쿼리를 통해 순열을 탐색했다.

 

import java.util.*;
import java.io.*;
public class sol092 {
	static int n, m;
	static int[] arr, tree;
	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);
	}
	
	static int query(int node, int start, int end, long order) {
		if(start == end) {
			return start;
		}
		int mid = (start + end) / 2;
		if(order <= tree[2*node]) {
			return query(2*node,start, mid, order);
		}
		else {
			return query(2*node+1, mid+1, end, order-tree[2*node]);
		}
	}
    
	static long update(int start, int end, int node, int del) {
		tree[node]--;
		if(start == end) {
			return 0;
		}
		else {
			int mid = (start + end) / 2;
			if(del <= mid) {
				return update(start, mid, 2*node, del);
			}
			else {
				return update(mid+1, end, 2*node+1, del);
			}
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		tree = new int[1000000];
		long idx =1;
		init(1, n, 1);
		bw.write("<");
		for(int i = 0; i < n; i++) {
			int size = n-i;
			idx += m - 1;
			if(idx % size == 0) idx = size;
			else if(idx > size) idx %= size;
			int num = query(1, 1, n, idx);
			update(1, n, 1, num);
			if(i == n-1) bw.write(String.valueOf(num));
			else bw.write(String.valueOf(num)+", ");
		}
		bw.write(">");
		bw.flush();
		br.close();
		bw.close();
	}
}