[18870] (C++) 좌표 압축

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

코드

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int N;
pair<int,int> p;
vector<pair<int,int>> x;
vector<pair<int,int>> tmp;

bool compare(pair<int,int> a, pair<int,int> b){
	return a.first < b.first;
}

bool compare2(pair<int,int> a, pair<int,int> b){
	return a.second < b.second;
}

int main(){
	cin >> N;

	for(int i=0; i<N; ++i){
		int a;
		cin >> a;
		p.first = a;
		p.second = i;
		x.push_back(p);
	}
	
	stable_sort(x.begin(), x.end(),compare);

	tmp = x;

	int num = 0;

	for(int i=0; i<N; ++i){
		if(i == 0){
			x[i].first = num;
			num++;
		}
		else{
			if(tmp[i-1].first == tmp[i].first){
				x[i].first = x[i-1].first;
			}

			else{
				x[i].first =num;
				num++;
			}
		}
	}

	stable_sort(x.begin(), x.end(), compare2);

	for(int i=0; i<N; ++i){
		cout << x[i].first<<' ';
	}

	return 0;
	
}

문제 자체는 굉장히 쉬워보인다. 하지만 제한사항에 N이 10^6까지 커질수 있기 때문에 함부로 했다간 큰코 다친다.

이 문제는 O(N^2)으로 풀면 시간 초과가 걸리기 때문에 sort함수를 잘 이용해야 한다.

 

나 같은 경우엔 stable_sort를 이용해 풀어줬지만 unique와 erase함수를 사용하면 더쉽게 풀 수 있다.

+ unique, erase를 이용한 풀이는 나중에..