[ALGOSPOT] 삽입 정렬 뒤집기

https://algospot.com/judge/problem/read/INSERTION

알고리즘 해결 전략 2의 22장. 이진 검색 트리에서 소개되는 문제이다
Treap을 이용하여 풀기를 권장(?) 하고 있다
푸는 다른 방법도 있겠지만
이왕이면 탐색에 특화된 이진 검색 트리를 사용해보라는 것..!

Treap이 무엇일까

마침 스터디를 위해 준비했던 자료가 있어서 넣어보았따

이 문제는 삽입 정렬 시 각 원소가 왼쪽으로 이동했던 횟수를 통해
정렬 전 배열이 무엇이었는지 알아내는 문제이다

막막한 게 사실이라 또 다음과 같이 끄적여보았다

처음엔 배열의 앞에서 부터 접근하는 방식으로 보았다
ex1 쪽을 보면,
왼쪽으로 이동한 횟수가 0일 경우 자신보다 큰 숫자가 없고,
왼쪽으로 이동한 횟수가 1일 경우 자신보다 큰 숫자가 1개 있음.

이런 식으로 생각해보았는데, 중복되는 숫자가 있어서 터무니 없는 생각이었다

그래서 배열의 뒤에서 부터 접근해보았다
ex 2 쪽을 보면,
왼쪽으로 이동한 횟수가 3일 경우 한 가지 숫자만 추려졌고,
인덱스를 앞 쪽으로 이동할 수록 후보 숫자가 여러 개여도 앞에서 이미 사용한 걸
제외하면 한 개만 남았다.

그래서 ex2에서 봤던 뒤에서부터 접근하기를
ex1에서 해보았더니, 추가적인 예외없이 잘 적용되었다.

그 다음 이진 검색 트리 중에서도 변형인 트립을 사용해야하는 이유가 무엇일지 다시 생각해보았다.
(책에서 권장해서 쓰는 거지만 그래도 다시 한 번 이유를 생각해보았다!)

그 이유는, 만약 n이 5일 경우 1부터 5까지의 숫자를 트리에 집어 넣어야 하는데,
이렇게 오름차순과 같이 특정 순서로 집어넣는 경우 Skewed tree가 될 수 있기 때문이다

또한, Skewed tree의 경우 높이를 시간 복잡도로 가지는 이진 검색 트리의 성능에 영향을 주기 때문이다

---

그 다음 고민거리는
입력된 shift 배열을 뒤에서부터 접근해서, 트리에서 k번째 원소를 찾아올건데
원소를 찾고 삭제하면 그 'k'라는 숫자가 달라져야 한다는 것이었다

shift 배열이 0 1 1 2 3 일 때
뒤에서 부터 2번째, 3번째, 4번째, 숫자를 찾아오면 되는데
k번째 원소를 찾고 삭제하면 총 크기가 달라지므로 이 숫자로 바꾸어주어야 했다

내가 제일 약한 부분이라 고민을 하다 책을 참고했다

kth(root, i + 1 - shift[i])

위처럼 i + 1- shift[i] 인데, 이런 걸 어떻게 생각해내는지 다시 한 번 배웠다
나도 다음에는 뚝딱 생각해낼 수 있었으면..!

---

다음은 코드이다
Treap도 자료구조니까 헤더파일로 분리를 해주었다.

CODE

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#include "Treap.h"

void solution(int n, vector<int> & ans, int * left_shift);
int main(void)
{
    int testcase = 0;
    cin>>testcase;
    int n = 0;

    vector<vector<int>> answers(testcase);

    for(int i=0; i<testcase; i++)
    {    
        cin>>n;
        int left_shift[n];
        for(int j=0; j<n; j++)
        {
            cin>>left_shift[j];
        }
        
        solution(n, answers[i], left_shift);

    }

    vector<int> ::iterator iter;
    for(int i=0; i<testcase; i++)
    {
        for (iter = answers[i].begin(); iter != answers[i].end(); iter++)
        {
            cout << *iter << ' ';
        }
        cout << endl;
    }
    
    
    return 0;
}

void solution(int n, vector<int> & ans, int * left_shift)
{
    /* Treap 구성 */
    Node * root = NULL;
    
    for(int i=0; i<n; i++)
    {
        root = insert(root, new Node(i+1));
    }

    for(int i=n-1; i>= 0; i--)
    {
        int key = kth(root, (i+1-left_shift[i]))->key;
        ans.push_back(key);
        root = erase(root, key);
    }
    reverse(ans.begin(), ans.end());

}

아래는 Treap.h 이다

책에 있는 코드를 그대로 사용하였고,
중위순회할 수 있는 inorder 함수만 추가해주었다
근데 생각해보니 kth()로 조회하면 되었던 것..!

Node * root = NULL;
root = insert(root, new node(key))

사소한 거지만
insert에서 root가 NULL 일 경우 그냥 node를 반환해주기 때문에

실제 사용할 때, 위와 같이 바로 root를 NULL로 지정 후 반복문에서 함께 만들어도 된다

CODE

// header guard : 헤더 파일이 같은 파일에서 두 번 이상 포함되지 않게 해줌
#ifndef TREAP_H 
#define TREAP_H
#include <cstdlib>
#include <iostream>
#include <utility>

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

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


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

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

void inorder(Node* root)
{
    if(root != NULL)
    {
        inorder(root->left);
        cout<<root->key<<' ';
        inorder(root->right);
    }
    return;
}
#endif