2465 줄세우기

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

문제

---

N명의 사람들이 어떤 공연장에 입장하기 위해서 한 줄로 서 있다. 
줄 서 있는 각 사람은 자기 앞에 서 있는 사람들 중에서 자기보다 키가 작거나 같은 사람들의 수를 알고 있다. 
그러면, 이 수들을 표시하는 수열을 S라고 한다.
N명의 키 집합과 수열 S가 주어질 때, 원래 줄 서 있는 키 순서를 정확히 찾아내는 프로그램을 작성하시오. 
예를 들어서, 사람들의 키 집합이 다음과 같이 주어진다 (여기서, 같은 키의 사람들이 여러 명 존재할 수 있어서 중복이 포함된다). 
{120, 167, 163, 172, 145, 134, 182, 155, 167, 120, 119, 156}
또한 각 사람이 자기 앞에 있는 사람들 중에서 자기보다 키가 작거나 같은 사람들의 수를 표시하는 수열 S는 다음과 같이 주어진다. 
S :   0 1 0 0 3 2 6 7 4 6 9 4
그러면, 실제 줄 서 있는 사람들의 키 순서는 다음과 같다. 
134 167 120 119 156 120 167 182 155 163  172 145

---

입력

첫째 줄에는 전체 사람의 수 N (1<=N<=100,000)이 주어진다. 다음 N개의 줄에 사람들의 키를 나타내는 양의 정수가 하나씩 주어진다. 
여기서 모든 키들은 2*10^9이하이다. 그리고 마지막 줄에 수열 S가 한 줄로 주어진다. 단 그 수열의 수는 하나의 공백을 두고 나타난다.

---

출력

출력은 N개의 줄로 구성된다. N개의 줄 각각에 원래 줄 서 있는 사람들의 키를 순서대로 하나씩 출력한다.

---

예제 입력1

12
120
167
163
172
145
134
182
155
167
120
119
156
0 1 0 0 3 2 6 7 4 6 9 4

---

예제 출력1

134
167
120
119
156
120
167
182
155
163
172
145

---

• 노드 접근시 노드의 합에서 -1 해준다.
• 왼쪽 노드 접근 조건 : Position ≤ 왼쪽 노드의 합
• 오른쪽 노드 접근 조건 : Position > 왼쪽 노드의 합 → Postion = Position - 왼쪽 노드의 합

• 풀이 소스

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_2465 {
    static void init(int[] tree, int[] arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = 1;
            return;
        }
        int mid = (start + end) / 2;
        int leftNodeIdx = node * 2;
        int rightNodeIdx = node * 2 + 1;
        init(tree, arr, leftNodeIdx, start, mid);
        init(tree, arr, rightNodeIdx, mid + 1, end);
        tree[node] = tree[leftNodeIdx] + tree[rightNodeIdx];
    }

    static void update(int[] tree, int[] visit, int[] tall, int node, int start
                                                , int end, int index, int position) {
        tree[node]--;
        if (start == end) {
            visit[index] = tall[start];
            return;
        }
        int mid = (start + end) / 2;
        int leftNodeIdx = node * 2;
        int rightNodeIdx = node * 2 + 1;
        if (position <= tree[leftNodeIdx]) {
            update(tree, visit, tall, leftNodeIdx, start, mid, index, position);
            return;
        }
        if (position > tree[leftNodeIdx]) {
            update(tree, visit, tall, rightNodeIdx, mid + 1, end, index, position - tree[leftNodeIdx]);
            return;
        }
    }

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            int N = Integer.parseInt(br.readLine());

            int tall[] = new int[N + 1];
            int position[] = new int[N + 1];
            int visit[] = new int[N + 1];
            StringTokenizer st;
            int h = (int) Math.ceil(Math.log(N) / Math.log(2));
            int treeSize = (1 << (h + 1)) + 1;
            int tree[] = new int[treeSize];

            for (int i = 1; i <= N; i++) {
                st = new StringTokenizer(br.readLine());
                tall[i] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                position[i] = Integer.parseInt(st.nextToken());
            }
            tall = Arrays.stream(tall).sorted().toArray();
            init(tree, tall, 1, 1, N);
            for (int i = N; i >= 1; i--) {
                update(tree, visit, tall, 1, 1, N, i, position[i] + 1);
            }

            for (int i = 1; i <= N; i++) {
                bw.write(visit[i] + "\n");
            }
            bw.flush();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}