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

 

1) 문제설명

 

백준 Online Judge 18870번 좌표압축

https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

 

2) 해결방법

 

2개의 벡터에 인덱스와 값을 저장해서 값을 변환 한 뒤 인덱스에 맞게 다시 정렬하는 방법을 사용했다.

pair를 사용하여 두 개의 벡터 (v1, v2)를 선언, v1의 값을 오름차순으로 정렬한다.

오름차순으로 정렬한 v1에서 첫 번째 값과 두 번째 값이 같다면 같은 순위이고 두번째 값이 더 크다면 순위가 +1 되기 때문에

v2에 이 순위 값을 저장한다.

v2의 인덱스를 오름차순으로 바뀐 v1의 인덱스로 교체하고 v2의 인덱스를 오름차순으로 정렬한 뒤 v2를 출력한다.

 

v(인덱스, 값)

[오름차순(값)] v1 = (2,-10) (4,-9) (0,2) (1,4) (3,4)  => (-10-> 0), (-9->1), (0->2), (4->3), (4->3)으로 인덱스와 함께 v2에 저장

v2 = (2,0) (4,1) (0,2) (1,3) (3,3) => [인덱스를 기준으로 오름차순] v2 = (0,2) (1,3) (2,0) (3,3) (4,1)

v2의 값을 출력 = 2 3 0 3 1

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;

/*
좌표압축
2개의 벡터에 인덱스와 값을 저장해서 값을 변환 한 뒤 인덱스에 맞게 다시 정렬하는 방법을 사용했다.
pair를 사용하여 두개의 벡터 (v1,v2)를 선언, v1의 값을 오름차순으로 정렬한다.
오름차순으로 정렬한 v1에서 첫번째 값과 두번째 값이 같다면 같은 순위이고 두번째 값이 더 크다면 순위가 +1 되기때문에
v2에 이 순위 값을 저장한다.
v2의 인덱스를 오름차순으로 바뀐 v1의 인덱스로 교체하고 v2의 인덱스를 오름차순으로 정렬한 뒤 v2를 출력한다.
*/

bool compare(pair<int, int>v1,pair<int, int>v2) {
	return v1.second < v2.second;
}
bool compare2(pair<int, int>v1, pair<int, int>v2) {
	return v1.first < v2.first;
}
int main() {
	int n;
	vector <pair<int, int>> v1;
	vector <pair<int, int>> v2;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		v1.push_back({ i,a }); // v1 (순서, 값)
		v2.push_back({ i,a }); // v2 (순서, 값)
	}
	sort(v1.begin(), v1.end(), compare); // v1값을 오름차순(2,-10) (4,-9) (0,2) (1,4) (3,4)
	int cnt = 0; // 
	for (int i = 0; i < n; i++) {
		v2[i].first = v1[i].first; // v2의 순위를 v1으로 교체한다. 0 1 2 3 4 -> 2 4 0 1 3
		v2[i].second = cnt; // (2,0) (4,1) (0,2) (1,3) (3,3)
		if (i < n - 1) {
			if (v1[i].second < v1[i+1].second) { // 오름차순으로 정렬한 값에서 다음값이 더 크다면
				cnt++; // 순위
			}
		}
	}
	sort(v2.begin(), v2.end(), compare2); // v2의 순서를 오름차순으로 정렬한다. (0,2) (1,3) (2,0) (3,3) (4,1)
	for (int i = 0; i < n; i++) {
		cout << v2[i].second << ' '; // v2[2].se = 2 v2[4].se
	}
	
}