https://www.acmicpc.net/problem/1849
1849번: 순열
1부터 N까지의 수들이 한 번씩 쓰인 수열이 있다. 그 수열에서 i 앞에 있는 수 들 중, i보다 큰 수들의 개수를 A[i]라고 정의하자. A[i]가 주어져 있을 때, 원래 수열을 구하는 프로그램을 작성하여라
www.acmicpc.net
사탕 상자 문제와 비슷한 방법인 구간합을 이용하여 해결하였습니다.
https://emoney96.tistory.com/93 (사탕 상자 문제풀이)
먼저 1 ~ N 만큼의 리프노드가 모두 1로 이루어진 세그먼트 트리를 구합니다.
입력으로는 1 ~ N 까지 자신보다 왼쪽에 있는 수 중에 자신보다 큰 수의 갯수가 주어집니다.
가장 작은 숫자인 1부터 입력으로 주어진 자신보다 큰 수의 갯수 + 1이 되는 자리를 찾습니다.
만약 cnt[1] = 5면 1의 자리는 6이 됩니다.
자리를 찾게 되면 해당 자리의 리프노드의 값을 0으로 하고 구간 값도 갱신합니다.
이 과정을 반복한 후에 결과를 출력해주시면 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
#include <iostream>
#define MAX 100000
using namespace std;
int list[MAX + 1], tree[(MAX + 1) * 4];
int cnt[MAX + 1];
int N;
int init(int node, int s, int e) {
if (s == e) {
return tree[node] = 1;
}
int m = (s + e) / 2;
return tree[node] = init(node * 2, s, m) + init(node * 2 + 1, m + 1, e);
}
void query(int node, int s, int e, int idx, int k) {
if (s == e) {
tree[node] = 0;
list[s] = idx;
return;
}
int m = (s + e) / 2;
if (k <= tree[node * 2]) query(node * 2, s, m, idx, k);
else query(node * 2 + 1, m + 1, e, idx, k - tree[node * 2]);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
void func() {
for (int i = 1; i <= N; i++) {
query(1, 1, N, i, cnt[i] + 1);
}
for (int i = 1; i <= N; i++) {
cout << list[i] << '\n';
}
}
void input() {
cin >> N;
init(1, 1, N);
for (int i = 1; i <= N; i++) {
cin >> cnt[i];
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > SegmentTree' 카테고리의 다른 글
| boj 16993 연속합과 쿼리 (0) | 2022.08.29 |
|---|---|
| boj 12846 무서운 아르바이트 (0) | 2022.08.19 |
| boj 14719 빗물 (0) | 2021.03.15 |
| boj 2304 창고 다각형 (0) | 2021.02.25 |
| boj 14438 수열과 쿼리 17 (0) | 2021.02.21 |