[ALGOSPOT] 삽입 정렬 뒤집기 (INSERTION)

algospot.com/judge/problem/read/INSERTION

algospot.com :: INSERTION

<문제>

유명한 정렬 알고리즘인 삽입 정렬은 정렬된 부분 배열을 유지하며 이 배열에 새 원소를 삽입해 나가는 식으로 동작합니다. 주어진 정수 배열 A를 정렬하는 삽입 정렬의 구현은 다음과 같습니다.

삽입 정렬은 A[0..i-1] 이 정렬된 배열일 때, A[i] 를 적절한 위치를 만날 때까지 왼쪽으로 한칸씩 움직입니다. 예를 들어 A={5,1,4,3,2} 의 삽입 정렬은 다음과 같이 이루어집니다.

A비고

5 1 4 3 2	초기 상태
1 5 4 3 2	1을 왼쪽으로 1칸 옮김
1 4 5 3 2	4를 왼쪽으로 1칸 옮김
1 3 4 5 2	3을 왼쪽으로 2칸 옮김
1 2 3 4 5	2를 왼쪽으로 3칸 옮김

1부터 N까지의 자연수가 한 번씩 포함된 길이 N 인 수열 A[] 를 삽입 정렬했습니다. 원래 수열은 알 수 없지만, 그 과정에서 각 원소가 왼쪽으로 몇 칸이나 이동했는지를 알고 있습니다. 예를 들어, 위 예제에서 각 위치에 있는 값들이 움직인 칸수를 표현하면 {0,1,1,2,3} 이 됩니다. 이 때 원래 수열을 찾아내는 프로그램을 작성하세요.

 

<입력>

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 원 배열의 길이 N (1 <= N <= 50000) 이 주어집니다. 그 다음 줄에 N 개의 정수로 A의 각 위치에 있던 값들이 움직인 칸수가 주어집니다. A 는 1부터 N 까지의 정수를 한 번씩 포함합니다.

입력의 양이 많으므로 가능한 빠른 입력 함수를 사용하는 것이 좋습니다.

 

<출력>

각 테스트 케이스마다 재구성한 A[] 를 한 줄에 출력합니다.

 

<예제 입력>

2

5

0 1 1 2 3

4

0 1 2 3

 

<예제 출력>

5 1 4 3 2

4 3 2 1

 

<아이디어>

삭제와 검색을 O(1)~O(logN) 만에 수행해야하며, 해당 요소가 몇번째 요소인지 찾을 수 있어야하는 문제입니다.

set 또는 map을 사용할 경우, 삭제와 검색을 O(logN)만에 수행할 수 있지만, 해당 요소가 몇번째 요소인지 계산하려면 begin()부터 해당 요소의 iterator까지 돌아야합니다.

그렇게 진행할 경우 최종 시간복잡도는 O(N^2logN) 까지 나오니 무조건 시간초과가 나오는 상황이죠...

 

다른 컨테이너를 조합해 위 조건을 만족시키는 방법을 찾으려 했으나 아직은 찾지 못했고, 결국 종만북에 소개되어있는 '트립'으로 문제를 해결할 수 있었습니다.

 

 

#include <bits/stdc++.h>
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
using namespace std;
typedef long long lld;
 
int n, shifted[50001];
int A[50001];
 
typedef int KeyType;
 
 
struct Node
{
    KeyType key;
 
    int priority, size;
 
    Node *left, *right;
 
    Node(const KeyType& _key) : key(_key), priority(rand()),
        size(1), left(NULL), right(NULL) {}
    void setLeft(Node* newLeft) { left = newLeft; calcSize(); }
    void setRight(Node* newRight) { right = newRight; calcSize(); }
    void calcSize()
    {
        size = 1;
        if (left) size += left->size;
        if (right) size += right->size;
    }
};
 
Node* lowerBound(Node* root, KeyType key)
{
    if (root == NULL) return NULL;
    if (root->key < key) return lowerBound(root->right, key);
    Node* ret = lowerBound(root->left, key);
    if (!ret) ret = root;
    return ret;
}
 
bool exists(Node* root, KeyType key)
{
    Node* node = lowerBound(root, key);
    return node != NULL && node->key == key;
}
 
Node* kth(Node* root, int k)
{
    int ls = (root->left ? root->left->size : 0);
    int rs = (root->right ? root->right->size : 0);
    if (k <= ls) return kth(root->left, k);
    if (k == ls + 1) return root;
    return kth(root->right, k - ls - 1);
}
 
int countLessThan(Node* root, KeyType key)
{
    if (root == NULL) return 0;
    if (root->key >= key)
        return countLessThan(root->left, key);
    int ls = (root->left ? root->left->size : 0);
    return ls + 1 + countLessThan(root->right, key);
}
 
typedef pair<Node*, Node*> NodePair;
 
 
NodePair split(Node* root, KeyType key)
{
    if (root == NULL) return NodePair(NULL, NULL);
 
    if (root->key < key)
    {
        NodePair rs = split(root->right, key);
        root->setRight(rs.first);
        return NodePair(root, rs.second);
    }
 
    NodePair ls = split(root->left, key);
    root->setLeft(ls.second);
    return NodePair(ls.first, root);
}
 
Node* insert(Node* root, Node* node)
{
    if (root == NULL) return node;
    if (root->priority < node->priority)
    {
        NodePair splitted = split(root, node->key);
        node->setLeft(splitted.first);
        node->setRight(splitted.second);
        return node;
    }
    else if (node->key < root->key)
        root->setLeft(insert(root->left, node));
    else
        root->setRight(insert(root->right, node));
    return root;
}
 
Node* merge(Node* a, Node* b)
{
    if (a == NULL) return b;
    if (b == NULL) return a;
 
    if (a->priority < b->priority)
    {
        b->setLeft(merge(a, b->left));
        return b;
    }
    a->setRight(merge(a->right, b));
    return a;
}
 
Node* erase(Node* root, KeyType key)
{
    if (root == NULL) return root;
    if (root->key == key)
    {
        Node* ret = merge(root->left, root->right);
        delete root;
        return ret;
    }
    if (key < root->key)
        root->setLeft(erase(root->left, key));
    else
        root->setRight(erase(root->right, key));
    return root;
}
void solve()
{
    Node* candidates = NULL;
    for (int i = 0; i < n; i++)
        candidates = insert(candidates, new Node(i + 1));
    for (int i = n - 1; i >= 0; --i)
    {
        int larger = shifted[i];
        Node*k = kth(candidates, i + 1- larger);
        A[i] = k->key;
        candidates = erase(candidates, k->key);
    }
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tc;
    cin >> tc;
    while (tc--)
    {
 
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> shifted[i];
        solve();
        for (int i = 0; i < n; i++)
            cout << A[i] << " ";
        cout << "\n";
 
    }
    return 0;
}