[백준] 1849 순열

문제 링크 : www.acmicpc.net/problem/1849

1849번: 순열

문제 유형

Segment Tree, 누적 합

 

문제에서 제시된 예제를 풀어보자.

이러한 과정을 통해 모든 수의 빈칸을 채우면 원하는 수열을 구할 수 있다.

하지만 이를 선형 탐색의 형태로 구현한다면 시간복잡도는 O(N^2)가 되므로, 주어진 시간 제한을 만족할 수 없다.

따라서, 각 수가 들어갈 인덱스를 찾는 데 적어도 O(logN) 의 시간복잡도를 가지도록 구현해야 한다. 전체 시간복잡도는 O(NlonN)이 된다.

이를 위해 세그먼트 트리를 사용한다.

 

각 세그먼트 트리의 모든 리프 노드를 1로 설정한다. 이는 그 칸이 빈 칸이라는 것을 의미한다.

따라서 맨 위의 root 노드에는 모든 구간에서 사용 가능한 빈 칸의 개수가 저장될 것이다.

만약 임의의 수 k에 대해, A[k] = X 라 하자. 우리는 세그먼트 트리를 통해 앞에서부터 사용 가능한 빈칸의 개수를 logN의 시간만에 찾아낼 수 있다.

① 우선 왼쪽 자식 노드의 빈칸 개수를 확인한다. 이 값을 left라 하자.

② 만약 left가 X보다 크다면, 우리가 찾는 k의 인덱스는 왼쪽 서브트리가 포함하는 구간 중 하나라는 것을 알 수 있다. 따라서, 왼쪽 서브트리에 대해 재귀한다.

③ 만약 X가 left보다 같거나 크다면, 우리가 찾는 k의 인덱스는 오른쪽 서브트리가 포함하는 구간 중 하나라는 것을 알 수 있다. 따라서, 오른쪽 서브트리에 대해 재귀한다. 단, 왼쪽 서브트리의 빈칸 값을 계산해야 하므로, X - left 번째 값을 찾도록 한다.

이러한 쿼리는 [백준] 2243 사탕 상자 문제와도 비슷하다. 누적합을 이용한 쿼리를 구현해 원하는 인덱스를 찾으면 된다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
 
#define MAXSIZE 100001
 
using namespace std;
typedef pair<int, int> p;
 
int n, diff_arr[100001], res_arr[100001];
int segtree[MAXSIZE * 4];
 
void create_segtree(int node, int start, int end) {
    if (start == end) {
        segtree[node] = 1;
        return;
    }
    int mid = (start + end) / 2;
    create_segtree(node * 2, start, mid);
    create_segtree(node * 2 + 1, mid + 1, end);
    segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];
}
 
void update(int node, int start, int end, int target) {
    if (start > target || end < target) return;
 
    if (start == end) {
        segtree[node] = 0;
        return;
    }
 
    int mid = (start + end) / 2;
    update(node * 2, start, mid, target);
    update(node * 2 + 1, mid + 1, end, target);
    segtree[node] -= 1;
}
 
int query(int node, int start, int end, int diff) {
    //현재 수가 들어갈 자리를 찾아 반환한다.
    if (start == end) return start;
    
    int mid = (start + end) / 2;
    int left = segtree[node * 2];    //왼쪽 서브트리의 구간합
 
    if (left > diff) {
        //왼쪽 서브트리에 남은 빈칸의 개수가 원하는 diff보다 많을 경우
        return query(node * 2, start, mid, diff);
    }
    else {
        //그렇지 않다면, 오른쪽 서브트리에서 값을 구한다.
        return query(node * 2 + 1, mid + 1, end, diff - left);
    }
}
 
void init() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> diff_arr[i];
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    create_segtree(1, 1, n);
    for (int i = 1; i <= n; i++) {
        int idx = query(1, 1, n, diff_arr[i]);
        res_arr[idx] = i;
        update(1, 1, n, idx);
    }
 
    for (int i = 1; i <= n; i++) printf("%d\n", res_arr[i]);
 
    return 0;
}