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

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

좌표 압축이란? 간단하게 말해서 존재하는 좌표 중 비교하는 자신보다 낮은 좌표의 갯수를 대신 출력하는 것이다.

 

입력이 2 4 1 3 이라고 하면 압축 시 1 3 0 2 가 되는 것이다.

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	vector<int> list;
	vector<int> solve;
	
	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		int temp;
		cin >> temp;

		list.push_back(temp);
		solve.push_back(temp);
	}

	sort(solve.begin(), solve.end());
	solve.erase(unique(solve.begin(), solve.end()), solve.end());

	for (int i = 0; i < N; i++)
		cout << lower_bound(solve.begin(), solve.end(), list[i]) - solve.begin() << " ";

	cout << '\n';

	return 0;
}

기준 좌표보다 작은 좌표가 몇개 있는지를 알기 위해서는 정렬과 중복값을 제거할 필요가 있다.

 

unique를 사용하게 되면 벡터 내의 중복 값들을 전부 벡터의 뒤로 이동시킨다.

예를 들어, 1 1 2 3 1 2 가 있다면 unique를 사용 후 1 2 3 1 2 2 가 되는 것이다.

 

erase를 사용하여 unique로 인해 반환된 위치부터 끝 위치까지의 쓰레기값들을 제거해준다.

 

이 후 lower_bound - 시작지점 을 통해 찾고 싶은 값의 인덱스를 얻을 수 있다.

 

이를 출력하면 정답값이 출력된다.