[BOJ] 18870 : 좌표 압축

Question

---

Solution

• 좌표들을 vector에 저장
• 각 좌표의 순위를 나타낼 vector를 복제
• 복제한 vector를 오름차순 정렬시키고 unique()와 erase() 이용하여 중복되는 수 제거
• lower_bound()를 이용해 index(순위)를 반환하여 출력한다

---

Cord

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

using namespace std;

vector<int> vCoord;

int main()
{
	// 좌표 수 입력
	int nums;
	cin >> nums;

	for (int idx = 0; idx < nums; idx++)
	{
		int coord;
		cin >> coord;
		vCoord.push_back(coord);
	}

	vector<int> vRank(vCoord);

	// 오름차순 정렬
	sort(vRank.begin(), vRank.end());

	// 중복값 제거
	vRank.erase(unique(vRank.begin(), vRank.end()), vRank.end());

	// 출력
	for (int idx = 0; idx < nums; idx++)
	{
		int rank = lower_bound(vRank.begin(), vRank.end(), vCoord[idx]) - vRank.begin();
		cout << rank << ' ';
	}

	return 0;
}

---

Result

---

What`s new

i번째 원소를 지우고 싶으면 vector의 시작부터 i를 더하면 된다.
또한, 범위를 지정하여 지울 수 있다.

v.erase(v.begin() + i); // 지정 원소 제거
v.erase(v.begin(), v.begin() + i) // 시작부터 i까지의 원소 제거

배열에서 중복되지 않는 원소들을 앞에서부터 채운다.
나머지 원소들은 그 뒤에 쌓이고 반환 값은 그 첫번째 원소의 주소이다.

unique(v.begin(), v.end());

배열에서 범위 내의 원소들 중 i 값 보다 크거나 같은 첫 번째 원소의 주소를 반환한다
vector가 정렬되어 있어야 한다.

lower_bound(v.begin(), v.end(), i); // 주소를 반환
Lower_bound(v.begin(), v.end(), i) - v.begin() // index 반환