[백준 - 18870] 좌표 압축

#include <iostream>
#include <algorithm>

#define MAX 1'000'002
using namespace std;

pair<int, int> arr[MAX];

bool comp(const pair<int, int> & a, const pair<int, int> & b)
{
	return a.second < b.second;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	int N; cin >> N;

	for (int i = 0; i < N; ++i)
	{
		cin >> arr[i].first;
		arr[i].second = i;
	}
	sort(arr, arr + N);

	int std = 0;
	for (int i = 0; i < N; ++i)
	{
		//바로 오른쪽이 자신과 같은지 
		if (arr[i].first == arr[i + 1].first) arr[i].first = std;
		else arr[i].first = std++;
	}
	sort(arr, arr + N, comp);
	
	for (int i = 0; i < N; ++i)
	{
		cout << arr[i].first << " ";
	}
		
	return 0;
}

---

||사고 과정

문제의 Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

는 말이 이해하기 힘들었지만 그냥 최소값부터 압축하라는 뜻..

 

Upper bound, Lower bound를 공부하면서 보게 된 문제여서 처음에는 Upper bound를 이용해서 풀려고했지만

1, 2, 3, 4, 5 처럼 중복되는 수가 없는 경우면 매 수마다 Upper bound를 하게 되니까 비효율적이라 생각해서

바로 옆에 있는 수를 비교해서 압축하는게 오히려 나을 수도 있겠다고 생각이 들어서 이렇게 풀게 됐다.

---

||더 나은 풀이

#include <iostream>
#include <algorithm>

#define MAX 1'000'002
using namespace std;

pair<int, int> arr[MAX];
int result[MAX];

bool comp(const pair<int, int> & a, const pair<int, int> & b)
{
	return a.second < b.second;
}


int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	int N; cin >> N;

	for (int i = 0; i < N; ++i)
	{
		cin >> arr[i].first;
		arr[i].second = i;
	}
	sort(arr, arr + N);

	int std = 0; 
	for (int i = 1; i < N; ++i)
	{
		if (arr[i].first != arr[i - 1].first) ++std;
		result[arr[i].second] = std;
	}
	
	for (int i = 0; i < N; ++i)
	{
		cout << result[i]<< " ";
	}
		
	return 0;
}

다른 사람들의 코드를 보던 중에 내 코드에서 sort한번을 생략 할 수 있음을 알았다.

 

배열을 하나 더 추가해서 arr[i]의 원래 순서의 인덱스에 넣는 방법이였다.

=> result[arr[i[.second] = std;

 

다른 문제에서 이렇게 원래 순서를 sort해서 가져오는 경우가 종종있었는데 앞으로 좀 더 빠르게 구현할 수 있겠다.

 

추가로 lower_bound를 이용해 푸는 방법으로 바킹독님 코드를 빌려왔다.

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

using namespace std;

int n;
int x[1000005];
vector<int> uni; // unique
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x[i];
		uni.push_back(x[i]);
	}
	sort(uni.begin(), uni.end());
	uni.erase(unique(uni.begin(), uni.end()), uni.end());
	for (int i = 0; i < n; i++)
		cout << lower_bound(uni.begin(), uni.end(), x[i]) - uni.begin() << ' ';
}

정렬 후 중복제거를 하게 되면 각 인덱스가 좌표압축한 결과와 같아진다.

ex) 

원본 배열 : [3] [2] [3] [3] [2] [4]

정렬 후 중복제거 : [2] [3] [4]

 

여기서 [2]는 인덱스가 0으로 2를 좌표압축한 결과와 같고 3, 4 도 마찬가지다.

이분탐색은 인덱스의 위치를 알 수 없으니 lower_bound로 그 위치를  알아내서 풀이하는 방법