[백준 18870] 좌표 압축

풀이

1. 벡터 입력 받고 원본 벡터(x)를 복사한 다른 벡터(solve)를 만든다

2. 복사한 벡터를 오름차순으로 정렬하고, erase, unique 함수를 사용하여 중복값을 제거한다

3. lower_bound 함수를 사용하여 2번 처리한 벡터에서 x[i] 값들이 몇번째에 위치하는지 확인한다

4. lower_bound 함수는 주소값을 반환하므로, 2번 처리한 벡터 solve의 시작 주소값을 빼서 출력

 

C++ erase, unique, lower_bound

1. erase: 말 그대로 벡터의 값을 지움

2. unique: 중복되지 않는 원소들을 앞에서부터 채워나가는 역할. 따라서 남은 뒷부분은 그대로 vector 원소값이 존재한다.

=> 두 함수를 함께 사용하면 중복값을 지울 수 있다.

3. lower_bound: Returns an iterator pointing to the first element in the container which is not considered to go before val. 원소가 저장된 공간 주소의 시작값을 반환한다.

 

정답 코드

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

int n;

int main(void) {
	
	cin >> n;

	vector<int> x(n);
	for (int i = 0; i < n; i++) {
		cin >> x[i];
	}

	vector<int> solve(x); // 원본 벡터 복사

	// 벡터 복사되는 부분 확인
	/*
	* 	for (int i = 0; i < solve.size();  i++) {
		cout << solve[i] << ' ';
	}
	cout << '\n';	
	*/


	sort(solve.begin(), solve.end()); // 오름차순 정렬
	solve.erase(unique(solve.begin(), solve.end()), solve.end()); // 중복값 제거
	for (int i = 0; i < n; i++) {
		// 원본 벡터 x의 i번째 원소가
		// 복사본 solve에서 몇번째에 위치하는지 확인한다
		// lower_bound는 주소값을 반환한다
		auto it = lower_bound(solve.begin(), solve.end(), x[i]);

		// lower_bound의 반환값에 solve의 시작 주소값을 빼면 답이 된다
		cout << it - solve.begin() << ' ';
	}

	return 0;
}