[18870] 좌표 압축

N의 조건, Xi의 조건이 명시되어 있다

 

처음에는 집합이 오름차순 정렬, 중복 제거가 되는 장점이 있어 아래와 같이 코드를 구현해보았다

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

int N;
int A[1000000];
set<int> B;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
		B.insert(A[i]);
	}
    
	for (int i = 0; i < N; i++)
	{
		set<int>::iterator iter = B.begin();
		int j = 0;
		for (iter;; iter++) {
			if ((*iter) == A[i]) {
				printf("%d ", j);
				break;
			}
			j++;
		}
	}
}

근데 시간초과가 떴다

 

그래서 quick sort를 이용하였다

quick sort란 분할, 정복, 결합을 이용하여 정렬하는 알고리즘이다

pivot을 기준으로 두 개의 분할된 부분 리스트를 정렬하고, 두  개의 정렬된 부분 리스트를 합하여 전체의 정렬된 리스트를 만드는 것이다

 

그리고 구조체를 이용하였다

num, rank, original을 담아서 

num : 입력된 수

rank : 정렬된 순서

original : 입력된 순서

를 나타냈다

 

처음에 한 정렬은 num(입력된 수)을 기준으로 정렬하였다

그 다음 for문을 이용하여 rank에 정렬된 순서를 0부터 담아주었다

 

그 다음 원래 original(입력된 순서)를 기준으로 다시 정렬하였다

그리고 rank를 출력하면 원래 입력된 순서의 정렬 순서가 차례대로 출력이 된다

 

 

완성된 코드는 다음과 같다

#include <iostream>
using namespace std;

int N;

struct mm {
	int num;
	int rank;
	int original;
};

mm B[1000000];

void quick_sort1(int left, int right) {
	if (left >= right)return;
	int p_right = right;
	int p_left = left;

	int pivot = B[(left + right) / 2].num;

	while (p_left <= p_right) {
		while (B[p_left].num < pivot) { p_left++; }
		while (pivot < B[p_right].num) { p_right--; }
		if (p_left <= p_right) {
			swap(B[p_left], B[p_right]);
			p_left++; p_right--;
		}
	}
	quick_sort1(left, p_right);
	quick_sort1(p_left, right);
}

void quick_sort2(int left, int right) {
	if (left >= right)return;
	int p_right = right;
	int p_left = left;

	int pivot = B[(left + right) / 2].original;

	while (p_left <= p_right) {
		while (B[p_left].original < pivot) { p_left++; }
		while (pivot < B[p_right].original) { p_right--; }
		if (p_left <= p_right) {
			swap(B[p_left], B[p_right]);
			p_left++; p_right--;
		}
	}
	quick_sort2(left, p_right);
	quick_sort2(p_left, right);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> B[i].num;
		B[i].original = i;
	}

	// num 기준으로 정렬
	quick_sort1(0, N - 1);

	// rank
	int before = B[0].num;
	int rank = 0;
	for (int i = 1; i < N; i++) {
		if (before == B[i].num) {
			B[i].rank = rank;
		}
		else {
			rank++;			
			B[i].rank = rank;
		}
		before = B[i].num;
	}

	// 원래 입력됐던 순서대로 정렬
	quick_sort2(0, N - 1);

	for (int i = 0; i < N; i++)
	{
		printf("%d ", B[i].rank);
	}
}