[ICPC] 백준 1849 - 순열

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

 

번역은 너무 간단히 쓰여 있어서 원문을 보는게 문제 이해를 더 쉽게 할 수 있을지도 모른다.

문제 설명

주어진 숫자들을 배열 A라고 했을 때 A[i]는 배열의 0 ~ i - 1 index에서 자기보다 큰 숫자가 출현한 횟수를 나타낸다. 이 정보를 기반으로 원래의 순열을 복원하라.

풀이

1부터 N까지 차례대로 순열을 복원한다고 했을 때 "해당 숫자가 위치하는 곳 왼쪽에서 채워지지 않은 index가 몇개가 되는가?"로 추적하여 복원을 할 수 있다.

 

그러면 세그먼트 트리를 이용하여 순열이 채워지지 않은 index는 1로 하여 트리를 초기화 할 수 있다.

 

그러면 현재 구간에서 비어있는 index의 개수를 구해 숫자가 들어갈 알맞는 위치를 찾는 질의 함수를 생각할 수 있다.

 

질의 함수는 왼쪽에 비어있는 index의 개수를 매개변수 k로 받아 k가 왼쪽 구간에 비어있는 index보다 많으면 오른쪽 구간, 그렇지 않으면 왼쪽 구간으로 가지치기를 하도록 하여 알맞은 index를 찾아가도록 구현하면 된다.

 

오른쪽 구간으로 갈 때는 왼쪽 구간에서 비어있는 index의 개수를 빼줘야 함을 잊지 말자.

 

질의를 통해 알맞은 위치를 찾으면 이를 저장하고 일반적인 세그먼트 트리의 update 함수를 통해 채워지지 않은 index 구간을 갱신하면 된다. (한 원소를 복원했으므로 해당하는 구간에서 1을 빼도록 한다.)

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int n;
int ar[100001];

inline int mid(int stt, int end) { return stt + (end - stt) / 2; }

int init(vector<int> &tree, int node, int start, int end)
{
    if (start == end) return tree[node] = 1;
    int m = mid(start, end);
    return tree[node] = init(tree, node * 2, start, m) + init(tree, node * 2 + 1, m + 1, end);
}

void update(vector<int> &tree, int node, int start, int end, int idx, int diff)
{
    if (idx < start || idx > end) return;

    tree[node] += diff;

    if (start != end)
    {
        int m = mid(start, end);
        update(tree, node * 2, start, m, idx, diff);
        update(tree, node * 2 + 1, m + 1, end, idx, diff);
    }
}

int query(vector<int> &tree, int node, int start, int end, int kth)
{
    if (start == end) return start;
    int m = mid(start, end);
    int stack_left = tree[node * 2];

    if (stack_left > kth) return query(tree, node * 2, start, m, kth);
    return query(tree, node * 2 + 1, m + 1, end, kth - stack_left);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;

    vector<int> segtree(n * 4);
    init(segtree, 1, 1, n);
    
    for (int i = 1; i <= n; ++i)
    {
        int x;
        cin >> x;
        int val = query(segtree, 1, 1, n, x);
        ar[val] = i;
        update(segtree, 1, 1, n, val, -1);
    }

    for (int i = 1; i <= n; ++i)
        cout << ar[i] << '\n';
}