[백준 1849번] [세그먼트 트리] 순열

문제 상황을 이해하려고 끄적거리다보면

숫자를 키워나가면서, 자기보다 앞에 있는 숫자들은 무시한채 채워지지 않은 공간의 갯수를 세면서 자리를 파악하는 것이 핵심이다.

 

즉, k를 채우기 위해서 1~N까지의 자리 중 1 ~ k - 1번째 숫자가 위치한 곳을 제외하고 앞에서부터 남는 자리의 갯수를 input값이랑 비교해주면 된다.

 

이 방법으로 문제를 풀려면 다음과 같은 조건이 필요하다.

1. 몇번째 index까지 고려했을 때 주어진 숫자를 만족할 수 있는지

2. 숫자를 채우고나서 위상의 변경을 빠르게 반영할 수 있는지

 

이 중 2번째 조건에서 세그먼트 트리의 change 함수에서의 역할과 비슷함을 느끼고, 세그먼트 트리로 접근방법을 잡았다.

또한, 몇번째 index까지 고려해야하는지를 생각해야하므로 부분합 구조와 비슷한 지점이 있다는 것을 쉽게 알 수 있다.

 

다만, 이 문제에서는 채워지지 않은 공간을 1, 채워진 공간을 0으로 취급하고 왼쪽칸을 중심으로 봐주어야하는 상황이므로 따로 함수를 짜서 정리해야 한다. 정확하게 문제에서 주어진 input값을 만족하는 상황을 찾되, 오른쪽을 바라볼 때는 왼쪽에서 tree에 저장된 값을 빼서 정리해야 한다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;

int tree[400004];
int data[100001];

int index_value;

int init(int start, int end, int node){
    if(start == end) return tree[node] = 1;
    int mid = (start + end) / 2;
    return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
}

void checker(int start, int end, int node, int check_num){
    if(tree[node] < check_num){
        return;
    }
    if(start == end){
        index_value = end;
        return;
    }
    int mid = (start + end) / 2;
    if(tree[node * 2] >= check_num ){
        checker(start, mid, node * 2, check_num);
    }
    else{
        checker(mid + 1, end, node * 2 + 1, check_num - tree[node * 2]);
    }
    return;
}

void update(int start, int end, int node, int index, int change_value){
    if(index < start || end < index) return; // 범위를 넘은 경우
    tree[node] += change_value;
    // 1칸짜리는 그냥 바로 리턴
    if(start != end){
        int mid = (start + end) / 2;
        update(start, mid, node * 2, index, change_value);
        update(mid + 1, end, node * 2 + 1, index, change_value);
    }
    return;
}

int main(void){
    fastio;
    int n;
    cin >> n;

    init(0, n - 1, 1);

    int data_store[100001];
    memset(data_store, 0, sizeof(data_store));

    for(int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        checker(0, n - 1, 1, temp + 1);
        update(0, n - 1, 1, index_value, -1);
        data_store[index_value] = i + 1;
    }

    for(int i = 0; i < n; i++){
        cout << data_store[i] << " ";
    }
    cout << "\n";
    return 0;
}