Java | 요세푸스 문제 2 [백준 1168]

나경호·2022년 4월 10일

Java boj 세그먼트트리

알고리즘 Algorithm

목록 보기

90/106

요세푸스 문제 2

출처 | 요세푸스 문제 2 [백준 1168]

문제

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

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

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

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 100,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

시간 제한

Java 8: 0.8 초
Python 3: 0.75 초
PyPy3: 0.75 초
Java 8 (OpenJDK): 0.8 초
Java 11: 0.8 초
Python 2: 0.75 초
PyPy2: 0.75 초
Kotlin (JVM): 0.8 초
Java 15: 0.8 초

풀이

import java.io.*;
import java.util.*;

public class Main{
    static int [] tree;
    //트리 초기화
    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, 2*node) + init(mid + 1, end, 2*node + 1);
    }

    // 트리 정보 수정
    public static int update(int start, int end, int node, int del) {
        // 트리를 1로 모두 초기화 했기 때문에 리프 노드의 상위 노드 경로를 지나며 개수 줄임
        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 int query(int start, int end, int node, int order) {
        // start와 end의 위치가 일치하면 번호를 반환
        if (start == end) { 
            return start;
        }
        int mid = (start + end) / 2;
        // 순서가 하위 노드의 시작보다 작을 때
        if (order <= tree[2*node]) {
            return query(start, mid, 2*node, order);
        }
        else {
            return query(mid + 1, end, 2*node + 1, order - tree[2*node]);
        }
    }
    
    
	public static void main(String[] args) throws IOException{

    BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st = new StringTokenizer(scan.readLine());

    int N = Integer.parseInt(st.nextToken());
    int K = Integer.parseInt(st.nextToken());
    tree = new int[N * 4];
    init(1, N, 1);

    int index = 1;
    StringBuilder sb = new StringBuilder("<");
        
    for (int i = 0; i < N; i++) {
        index += K - 1;
        // 사람 수
        int size = N - i; 

        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 + ", ");
        }
    }
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    }
}