[백준 18870번 / C++] 좌표 압축

unordered_map 자료구조를 활용해서 풀었다. 

 

#접근방법

1. 처음 입력받은 v라는 벡터의 데이터값들을 re_v에 옮겨닮는다.

2. re_v를 오름차순으로 정렬한 후 첫 번째 원소부터 살펴본다. 

3. 해당 원소를 key값으로 가지는 map의 값을 cnt로 저장한다. 

4. cnt는 해당 원소의 시작번호다. 즉, 이전에 같은 key 값을 가지고 있다면 그 번호로 세팅해 주어야한다. 

그래서 본인은 prev라는 변수를 사용하여 이전에 사용했던 값과 다른지 비교를 하고 다르다면 +1 을 한 번호로 세팅해준다. 

5. 이후 v라는 벡터의 원소를 key로 가진 map 의 value값을 출력하면 된다. 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std; 
int main() {
	ios::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0); 
	int n; cin >> n; 
	vector <int> v(n); 
	vector <int> re_v; 
	for (int i = 0; i < n; i++) cin >> v[i]; 	
	re_v = v; 
	sort(re_v.begin(), re_v.end()); 
	unordered_map <int, int> m;
	int prev = re_v[0];
	int cnt = 0; 
	m[re_v[0]] = cnt; 
	for (int i = 1; i < re_v.size(); i++) {
		if (prev != re_v[i])m[re_v[i]] = ++cnt;
		prev = re_v[i]; 
	}
	for (int i = 0; i < n; i++) {
		cout << m[v[i]] << " "; 
	}
}

 

18870번: 좌표 압축