[Algospot] 삽입 정렬 뒤집기 (문제 ID : INSERTION)

문제

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

void insertionSort(vector<int>& A) { for(int i = 0; i < A.size(); ++i) { // A[0..i-1] 에 A[i] 를 끼워넣는다 int j = i; while(j > 0 && A[j-1] > A[j]) { // 불변식 a: A[j+1..i] 의 모든 원소는 A[j] 보다 크다. // 불변식 b: A[0..i] 구간은 A[j] 를 제외하면 정렬되어 있다. swap(A[j-1], A[j]); --j; } } }

삽입 정렬은 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[] 를 한 줄에 출력합니다.

---

트립을 이용해서 해결하는 문제이다. 

트립에 1부터 N까지 수를 채운다.

그중 N부터 거꾸로 생각하며 N보다 큰 수가 몇개 있는지 구한후 역으로 생각하면 된다.

만약 N이 5까지 있는데 shift[4]가 3이라면 3만큼 왼쪽으로 옮긴 게 맞는 수라는 뜻이므로 A[4] = 2가 된다. 즉 x보다 큰 수가 3개 있다는 뜻이다.

이 점을 활용해서 문제를 해결한다.

 

 

C++ 코드 : https://github.com/chosh95/STUDY/blob/master/Algospot/INSERTION.cpp

chosh95/STUDY

코드 원본

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
int C, N, A[50001], shifted[50001];

struct Node {
	int key;
	int priority, size;
	Node* left, *right;
	Node(const int& _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, int 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);
	}
	else {
		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;
	}
	else {
		a->setRight(merge(a->right, b));
		return a;
	}
}

Node* erase(Node* root, int 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, int 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 solve() {
	Node* candidate = NULL;
	for (int i = 0; i < N; i++)
		candidate = insert(candidate, new Node(i + 1));
	for (int i = N - 1; i >= 0; i--) {
		int large = shifted[i];
		Node* k = kth(candidate, i + 1 - large);
		A[i] = k->key;
		candidate = erase(candidate, k->key);
	}
}

int main()
{
	cin >> C;
	while (C--) {
		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;
	}
}