🚀 [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 | 비고 |
|---|---|
| 51432 | 초기상태 |
| 15432 | 72 |
| 14532 | 4를 왼쪽으로 1칸 옮김 |
| 13452 | 3을 왼쪽으로 2칸 옮김 |
| 12345 | 2를 왼쪽으로 3칸 옮김 |
1부터 N까지의 자연수가 한 번씩 포함된 길이 N 인 수열 A[] 를 삽입 정렬했습니다. 원래 수열은 알 수 없지만, 그 과정에서 각 원소가 왼쪽으로 몇 칸이나 이동했는지를 알고 있습니다. 예를 들어, 위 예제에서 각 위치에 있는 값들이 움직인 칸수를 표현하면 {0,1,1,2,3} 이 됩니다. 이 때 원래 수열을 찾아내는 프로그램을 작성하세요.
🔑 [풀이]
뒤에서부터 문제를 풀면 쉽게 해결할 수 있는 문제였습니다.
마지막 숫자 A[N-1]이 왼쪽으로 몇 칸 움직였는지를 보면 A[N-1]에 어떤 숫자가 들어가야 하는지 알 수 있습니다.
이것들을 계산하기 위해서는 A[i] 에 들어갈 숫자들을 어떻게 저장 할 것인가, 후보들 중 k번째 원소를 찾고, 삭제하는 작업을 빠르게 해야 하기 떄문에 이진검색 트리를 이용합니다.
하지만 set과 map은 원소를 찾는 기능을 제공하지 않기 때문에, 이전에 배웠던 트립을 사용하여 문제를 해결합니다.
⌨️ 입력
입력의 첫 줄에는 테스트 케이스의 수 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
💎 전체 코드는 다음과 같습니다.
//
// INSERTION.cpp
// AALGGO
//
// Created by inhyeok on 2021/12/22.
//
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("INSERTION.txt");
int N;
const int MAXN = 50000;
int A[MAXN];
int shifted[MAXN];
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);
}
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(node->priority > root->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 일떄
Node* merge(Node* A, Node* B){
if(A == NULL) return B;
if(B == NULL) return A;
if(B->priority > A->priority){
B->setLeft(merge(A,B->left));
return B;
}
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;
}
else 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);
}
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--){
Node* k = kth(candidates, i - shifted[i] + 1 );
A[i] = k->key;
candidates = erase(candidates,k->key);
}
}
int main(){
int test_case;
fin >> test_case;
for(int test=0; test<test_case; test++){
fin >> N;
for(int i=0; i<N; i++){
fin >> shifted[i];
}
solve();
for(int i=0; i<N; i++){
cout << A[i] << " ";
}
cout << endl;
}
}
Comments