[백준OJ] 좌표 압축

www.acmicpc.net/problem/18870

18870번: 좌표 압축

---

 

-풀이-

먼저 입력받은 값들을 a와 b 모두 저장해준다음에, b를 정렬하고 중복값을 제거해준다.

그러면 중복값이 없는 오름차순 배열이 완성될텐데, 이 b벡터를 돌며 map에 순위를 저장시킨다.

마지막으로 a벡터를 돌며 해당 값에 따른 순위를 map에서 꺼내온다.

 

-시간복잡도-

정렬은 퀵소트를 사용했으므로 O(NlogN) 이되고, erase함수가 O(N) , unique함수가 O(N)이므로, 중복을 제거하는 로직은 O(N+N)=O(N)이 된다.

따라서 총 O(NlogN)이된다.

 

-코드-

 

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

int n;
vector<int> a, b;
map<int,int> m;

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int data;
		cin >> data;
		a.push_back(data);
		b.push_back(data);
	}

	sort(b.begin(), b.end());
	b.erase(unique(b.begin(), b.end()), b.end());
	for (int i = 0; i < b.size(); i++) {
		m[b[i]] = i;
	}
	for (int i = 0; i < n; i++) {
		cout << m[a[i]] << " ";
	}
}