[1849번] 순열

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 세그먼트 트리 :: http://www.crocus.co.kr/648

이 문제를 풀기 전에 우선 [2243번] 사탕 상자 :: http://www.crocus.co.kr/668 문제를 우선 풀어보는 것을 권장하고 싶다.

문제가 같은 내용으로 흘러가기 때문이다.

이 문제의 예제 입력을 보면 

8
5
0
1
2
1
2
0
0

 

라고 나와있는데 결국 a[1] = 5, a[2] = 0, ... a[8] = 0의 의미를 가지게 되고

1은 5번째에 2는 0번째에.. 8은 0번째에 위치해야 한다는 것을 알 수 있다.

따라서 채워지지 않은 공간 8개(n이 8이니)가 있다고 가정하고 이 문제를 아래 방식으로 보면 다음과 같다.

ㅁㅁㅁㅁㅁㅁㅁㅁ의 공간에서

1은 5번째 와야하니 

ㅁㅁㅁㅁ1ㅁㅁㅁ가 되고

2는 0번째에 와야하니

2ㅁㅁㅁ1ㅁㅁㅁ가 되고

3은 1번째에 와야하니

2ㅁ3ㅁ1ㅁㅁㅁ가 되고 이 과정을 반복하면 정답이 된다.

이때 3은 1번째에 와야하는데 왜 23ㅁ1ㅁㅁㅁ가아니고 2ㅁ3ㅁ1ㅁㅁㅁ이냐면 

채워지지 않은 공간 내에서 k번째에 위치하도록 하면 되기 때문이다.

이러한 방법으로 문제를 풀기 위해서는 이제 세그먼트 트리를 이용할 수 있게된다.

세그먼트 트리를 왜 쓰고있는지는  [2243번] 사탕 상자 :: http://www.crocus.co.kr/668  이 링크에서 공부해보길 추천한다.

소스 코드 : 

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 61 62 63 64 65 66 67 68 69 70 71 72 73 74

#include <iostream> #include <cstdio> #include <vector> #include <cmath>   using namespace std;   void update(vector<int> &tree, int node, int start, int end, int index, int diff) {     if (!(start <= index && index <= end))         return;       tree[node] += diff;       if (start != end)     {         int mid = (start + end) / 2;         update(tree, node * 2, start, mid, index, diff);         update(tree, node * 2 + 1, mid + 1, end, index, diff);     } }   int query(vector<int> &tree, int node, int start, int end, int val) {     int get = -1;     int mid = (start + end) / 2;       if (start == end)     {         tree[node]--;         return start;     }       if (tree[node * 2] >= val)         get = query(tree, node * 2, start, mid, val);       else         get = query(tree, node * 2 + 1, mid + 1, end, val - tree[node * 2]);       tree[node]--;     return get; } int main() {     int n;     scanf("%d", &n);       int h = (int)ceil(log2(n));     int tree_size = (1 << (h + 1));       vector<int> arr(n + 1);     vector<int> tree(tree_size);     vector<int> ans(n + 1);       for (int i = 0; i < n; i++)     {         scanf("%d", &arr[i]);         update(tree, 1, 0, n - 1, i, 1);     }       for (int i = 0; i < n; i++)     {         int get = query(tree, 1, 0, n - 1, arr[i] + 1);         ans[get + 1] = i + 1;     }       for (int i = 1; i <= n; i++)         printf("%d ", ans[i]);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus