[백준 1777번] [세그먼트 트리 / 이분 탐색] 순열복원

Approach

이 문제의 예시로 제공된 수에서 위치를 가장 판단하기 쉬운 것은 8이다.

왜 8이 가장 마지막 자리에 있는지를 생각해보면 자기보다 작은 수가 한 개도 없고, 가장 큰 숫자이므로 가장 뒤에 오는 것이다.

마찬가지로 7의 경우를 판단해보면 뒤에서부터 남은 자리 중 2개를 건너뛰고 앉으면 된다.

 

즉, 이를 통해 구간합을 관리하고 있다는 느낌을 받으면 된다.

추가적으로 큰 수부터 작은 수로 자리를 채워나가면서 업데이트 해주면 된다.

 

다만, 해당 자리가 어딘지를 판단해주기 위해서는 이분탐색으로 파악해주면 된다.

느낌이 https://viyoung.tistory.com/246 와 정말로 비슷하다. 이분탐색을 통해 쿼리의 인덱스를 찾는 느낌이 매우 유사하다.

[백준 19646번] [세그먼트 트리] Random Generator

따라서 모든 숫자에 대해서 판단하므로 N, 구간합 찾는데 lgN, 이분 탐색하는데 lgN이므로

이 문제를 풀기위한 시간 복잡도는 $O(N(lgN)^2)$이다.

Code

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

using namespace std;

// i 뒤에 존재하는 것 중, 1 ~ i - 1의 개수
// 즉, 가장 큰 수부터 작은 수 방향으로 진행
// 앞에 몇 개의 빈 자리가 있는지를 관리(구간합)
// 해당하는 자리에 계속 반복해서 넣음(Find by binary search)
// O(n(lgn)^2)이므로 시간 복잡도 측면에서도 충분

int seg[400000];
int N;

void update(int node_index, int node_left, int node_right, int index){
    if(index < node_left || node_right < index) return;
    
    if(node_left == node_right){
        seg[node_index] = 1;
        return;
    }
    else{
        int mid = (node_left + node_right) / 2;
        update(node_index * 2, node_left, mid, index);
        update(node_index * 2 + 1, mid + 1, node_right, index);
        seg[node_index] += 1;
        return;
    }
}

int query(int node_index, int node_left, int node_right, int query_left){
    int query_right = N;

    if(node_right < query_left || query_right < node_left) return 0;
    if(query_left <= node_left && node_right <= query_right) return seg[node_index];
    else{
        int mid = (node_left + node_right) / 2;
        return query(node_index * 2, node_left, mid, query_left) +
               query(node_index * 2 + 1, mid + 1, node_right, query_left);
    }
}

int main(void){
    fastio;
    memset(seg, 0, sizeof(seg));
    vector<int> d;
    
    cin >> N;

    for(int i = 0; i < N; i++){
        int t;
        cin >> t;
        d.push_back(t);
    }

    int position[N + 1];

    for(int i = N - 1; i >= 0; i--){
        int val = d[i];
        int start = 1;
        int end = N + 1;
        while(start < end){
            int mid = (start + end) / 2;
            if(N - mid - query(1, 1, N, mid) >= val){
                start = mid + 1;
            }
            else end = mid;
        }
        position[start - 1] = i + 1;
        update(1, 1, N, start - 1);
    }

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