Algospot INSERTION

문제 링크입니다: https://algospot.com/judge/problem/read/INSERTION

뒤에서부터 문제를 풀면 쉽게 접근할 수 있는 문제였습니다.

마지막 숫자 A[N-1]이 왼쪽으로 몇 칸 움직였는지를 보면 A[N-1]에 어떤 숫자가 들어가야 하는지 알 수 있기 때문입니다.

A[i]에 들어갈 수 있는 숫자들의 집합을 저장하기 위해 자료구조로 이진 탐색 트리를 사용할 수 있는데 알고리즘 문제를 풀 때는 직접 구현하는 것보다 보통 STL set나 map을 사용하지만 이들은 k번째 원소를 찾는 기능을 제공하지 않기 때문에 직접 구현한 자료구조 트립을 사용했습니다.

그냥 이진 탐색 트리를 구현했을 경우에는 오름차순이나 내림차순으로 자료가 제공이 된다면 linked list 형태를 띄기 때문에 탐색하는 시간복잡도가 O(logN)이 아닌 O(N)이 되기 때문에 비효율적이게 됩니다.

따라서, 트립은 key와 함께 우선순위도 저장하면서 우선순위가 제일 높은 key를 root로 만들어 linked list 형태를 형성할 확률을 최소화합니다.

물론, 우선순위는 rand() 함수를 통해 랜덤하게 부여받습니다!

#include <iostream>

#include <cstdlib>

#include <ctime>

using namespace std;

 

const int MAX = 50000;

 

typedef int KeyType;

//트립의 한 노드를 저장

struct Node

{

        //노드에 저장된 원소

        KeyType key;

        //이 노드의 우선순위

        int priority;

        //이 노드를 루트로 하는 서브트리의 크기

        int size;

        //두 자식 노드의 포인터

        Node *left, *right;

        //생성자에서 난수 우선순위를 생성하고, size와 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();

        }

        //size 멤버를 갱신한다

        void calcSize()

        {

                 size = 1;

                 if (left)

                         size += left->size;

                 if (right)

                         size += right->size;

        }

};

 

typedef pair<Node *, Node *> NodePair;

//root를 루트로 하는 트립을 key 미만의 값과 이상의 값을 갖는 두 개의 트립으로 분리

NodePair split(Node *root, KeyType key)

{

        if (root == NULL)

                 return NodePair(NULL, NULL);

        //루트가 key 미만이면 오른쪽 서브트리를 쪼갠다

        if (root->key < key)

        {

                 NodePair rs = split(root->right, key);

                 root->setRight(rs.first);

                 return NodePair(root, rs.second);

        }

        //루트가 key 이상이면 왼쪽 서브트리를 쪼갠다

        NodePair ls = split(root->left, key);

        root->setLeft(ls.second);

        return NodePair(ls.first, root);

}

 

//root를 루트로 하는 트립에 새 노드 node를 삽입한 뒤 결과 트립의 루트를 반환

Node *insert(Node *root, Node *node)

{

        if (root == NULL)

                 return node;

        //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;

}

 

//a와 b가 두 개의 트립이고 max(a)<min(b)일 때 이 둘을 합친다

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;

}

 

//root를 루트로 하는 트립에서 key를 지우고 결과 트립의 루트를 반환한다

Node *erase(Node *root, KeyType key)

{

        if (root == NULL)

                 return root;

        //root를 지우고 양 서브트리를 합친 뒤 반환한다

        if (root->key == key)

        {

                 Node *result = merge(root->left, root->right);

                 delete root;

                 return result;

        }

        if (key < root->key)

                 root->setLeft(erase(root->left, key));

        else

                 root->setRight(erase(root->right, key));

        return root;

}

 

//root를 루트로 하는 트리 중에서 k번째 원소를 반환한다

Node *kth(Node *root, int k)

{

        //왼쪽 서브트리의 크기를 우선 계산

        int leftSize = 0;

        if (root->left != NULL)

                 leftSize = root->left->size;

        if (k <= leftSize)

                 return kth(root->left, k);

        if (k == leftSize + 1)

                 return root;

        return kth(root->right, k - leftSize - 1);

}

 

//key보다 작은 키 값의 수를 반환

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);

}

 

int N;

int shifted[MAX];

int A[MAX];

 

//n, shifted[]를 보고 A[]에 값을 저장한다

void solve(void)

{

        //1~N까지의 숫자를 모두 저장하는 트립을 만든다

        Node *candidates = NULL;

        for (int i = 0; i < N; i++)

                 candidates = insert(candidates, new Node(i + 1));

        //뒤에서부터 A[]를 채워나간다

        for (int i = N - 1; i >= 0; i--)

        {

                 //후보 중 이 수보다 큰 수가 larger개 있다

                 int larger = shifted[i];

                 Node *k = kth(candidates, i + 1 - larger);

                 A[i] = k->key;

                 candidates = erase(candidates, k->key);

        }

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

 

        for (int i = 0; i < test_case; i++)

        {

                 cin >> N;

                 for (int i = 0; i < N; i++)

                         cin >> shifted[i];

 

                 solve();

                 for (int i = 0; i < N; i++)

                         cout << A[i] << " ";

                 cout << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략