순열복원

문제

문제 설명

1부터 N번까지로 수로 이루어진 순열이 있다.

그리고 이 순열과 연관된 "Inversion sequence"라고 부르는 수열이 있다. 이 수열의 i번째 원소에는 순열에서 i보다 뒤에 나오면서 i보다 작은 수의 개수가 들어간다.

2 4 5 1 7 6 3 8

위의 순열이 있다면 이것의 Inversion sequence는

0 1 0 2 2 1 2 0 이 된다.

문제는 역으로 어떤 Inversion sequence가 주어지면 이것에 해당하는 순열을 찾는 프로그램을 작성하는 것이다.

제한 사항

순열의 크기 N(1 ≤ N ≤ 100,000)이 주어진다. 두 번째 줄에는 순열 1, 2, …, N에 해당하는 Inversion sequence가 공백으로 구분되어 들어온다.

입력으로 주어진 Inversion sequence에 대응하는 순열을 공백으로 구분하여 한 줄에 출력한다.

입출력 예

입력	출력
8
0 1 0 2 2 1 2 0	2 4 5 1 7 6 3 8
8
0 1 2 3 4 5 6 7	8 7 6 5 4 3 2 1

제출 코드

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

// https://www.acmicpc.net/problem/1777
public class five1777 {
    public void solution() throws IOException {
        // 입력부
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(reader.readLine());
        long[] arr = new long[n];
        StringTokenizer infoToken = new StringTokenizer(reader.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Long.parseLong(infoToken.nextToken());
        }

        // 트리 만들기
        int h = (int) Math.ceil(Math.log(n) / Math.log(2));
        int size = (1 << (h + 1));
        long[] tree = new long[size];
        init(arr, tree, 1, 0, n - 1);

        // 뒤에서부터 접근
        long[] ans = new long[n];
        for (int i = n - 1; i >= 0 ; i--) {
            // 뒤에 남은 칸의 수로 접근하기
            int idx = query(tree, 1, 0, n - 1, arr[i]);
            ans[idx] = i + 1;
            // 채워진 칸 업데이트
            update(tree, 1, 0, n - 1, idx);
        }

        for(long val : ans) {
            writer.write(val + " ");
        }
        writer.flush();
    }

    private void update(long[] tree, int node, int start, int end, int idx) {
        if (start > idx || idx > end) {
            return;
        }
        tree[node]--;
        if (start != end) {
            update(tree, node * 2, start, (start + end) / 2, idx);
            update(tree, node * 2 + 1, (start + end) / 2 + 1, end, idx);
        }
    }

    private int query(long[] tree, int node, int start, int end, long val) {
        if (start == end) {
            return start;
        } else {
            if (val < tree[node * 2 + 1]) { // 뒤에 위치하는 작은 수가 오른쪽 노드보다 작을 때
                return query(tree, node * 2 + 1, (start + end) / 2 + 1,  end, val);
            } else {
                return query(tree, node * 2, start, (start + end) / 2, val - tree[node * 2 + 1]);
            }
        }
    }

    // 트리 초기화
    private void init(long[] arr, long[] tree, int node, int start, int end) {
        if (start == end) {
            tree[node] = 1;
        } else {
            init(arr, tree, node * 2, start, (start + end) / 2);
            init(arr, tree, node * 2 + 1, (start + end) / 2 + 1, end);
            tree[node] = tree[node * 2] + tree[node * 2 + 1];
        }
    }

    public static void main(String[] args) throws IOException {
        new five1777().solution();
    }
}