반응형
https://www.acmicpc.net/problem/1849
1849번: 순열
1부터 N까지의 수들이 한 번씩 쓰인 수열이 있다. 그 수열에서 i 앞에 있는 수 들 중, i보다 큰 수들의 개수를 A[i]라고 정의하자. A[i]가 주어져 있을 때, 원래 수열을 구하는 프로그램을 작성하여라
www.acmicpc.net
[ 문제풀이 ]
이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.
https://rudalsd.tistory.com/51
[ 자료구조 ] 세그먼트 트리 (Segment Tree)
1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1
rudalsd.tistory.com
1. 모든 리프 노드를 1로 초기화시킵니다.
2. 각 숫자의 값은 작은 숫자부터 앞의 빈칸의 수를 의미합니다. 따라서, 세그먼트 트리의 노드의 값이 빈칸의 수를 의미하고, 이 수가 현재 숫자의 값보다 크다면 해당 노드로, 작다면 노드의 값을 뺀 값을 가지고 다음 노드로 재귀합니다.
3. 리프노드에 도달하면 해당 위치에 현재 숫자가 있는 것이므로 ans [해당 위치] = 현재 숫자가 됩니다.
4. for문을 통해 1부터 N번 째 위치까지의 수를 출력합니다.
[ 소스코드 ]
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 59 60 | #include<iostream> using namespace std; int N; int arr[100001]; int segTree[263000]; int ans[100001]; void makeTree(int node, int s, int e) { if (s == e) { segTree[node] = 1; return; } int m = (s + e) / 2; makeTree(node * 2, s, m); makeTree(node * 2 + 1, m+1, e); segTree[node] = segTree[node * 2] + segTree[node * 2 + 1]; } void getTree(int node, int s, int e, int x, int i) { if (s == e) { segTree[node] = 0; ans[s] = i; return; } segTree[node] -= 1; int m = (s + e) / 2; if (segTree[node * 2] < x) { getTree(node * 2 + 1, m + 1, e, x - segTree[node * 2], i); } else { getTree(node * 2, s, m, x, i); } } int main() { scanf("%d", &N); for (int i = 1; i <= N; i++) { scanf("%d", &arr[i]); } makeTree(1, 1, N); for (int i = 1; i <= N; i++) { getTree(1, 1, N, arr[i] + 1, i); } for (int i = 1; i <= N; i++) { printf("%d\n", ans[i]); } } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 1615번 - 교차개수세기 (C++) (0) | 2023.01.21 |
|---|---|
| [ 백준 ] 1777번 - 순열복원 (C++) (0) | 2023.01.20 |
| [ 백준 ] 16975번 - 수열과 쿼리 21 (C++) (0) | 2023.01.18 |
| [ 백준 ] 10999번 - 구간 합 구하기 2 (C++) (0) | 2023.01.17 |
| [ 백준 ] 5676번 - 음주 코딩 (C++) (0) | 2023.01.15 |