백준 / 정렬 / 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을 공백 한 칸으로 구분해서 출력한다.

제한

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

예제 입력 1 

5
2 4 -10 4 -9

예제 출력 1 

2 3 0 3 1

 

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n;
	cin >> n;
	
	vector<int> v1, v2;
	
	for(int i=0; i<n; i++) {
		int num;
		cin >> num;
		
		v1.push_back(num);
	}
	
	v2 = v1;
	sort(v2.begin(), v2.end());
	v2.erase(unique(v2.begin(), v2.end()), v2.end());
	
	for(int i=0; i<n; i++) {
		int idx;
		auto it = lower_bound(v2.begin(), v2.end(), v1[i]);
		idx = it - v2.begin();
		
		cout << idx << " ";
	}
	
	return 0;
}

---

일단 문제를 처음보면 이해가 잘 안갈수도 있다.

문제 설명을 간단히 해보자면, 입력받은 수들에서 각각의 수보다 작은 수가 몇개인지 순서대로 출력하는 것이다.

 

따라서 수들을 입력받을 벡터와, 입력받은 수들을 정렬하고 중복을 지울 벡터를 2개 선언하였다.

입력받은 수들을 정렬하고 중복을 지우게 되면, 해당하는 수가 몇번째로 작은 수 인지 판단할 수 있기 때문이다.

 

예를들어 위의 예시처럼 2 4 -10 4 -9 를 입력받게 되면 v1에는 그대로 들어가고,

v2에는 -10 -9 2 4 가 들어가게 되는것이다.

따라서 v1에서 4보다 작은 수가 몇개인지 판단하려면 v2에서 볼경우 -10과 -9과 2이기 때문에 3개이다.

그런데 v2에서 4의 인덱스가 3이기 때문에 갯수는 인덱스와 같다는것을 알 수가 있다.

 

따라서 우리는 v2에서 해당하는 인덱스를 출력해주면 된다.

 

여기서 lower_bound가 사용되는데, lower_bound는 범위내에서 찾으려는 수보다 크거나 같은 수가 몇번째로

등장하는지 알 수 있게 해준다.

lower_bound에 대한 자세한 설명은 밑을 참조바랍니다.(추가예정)

 

그런데 lower_bound는 iterator를 반환하기 때문에 인덱스를 바로 알 수는 없고,

우리가 구한 iterator에서 시작 iterator를 빼주면 해당 인덱스를 구할 수 있다.