BOJ 18870 - 좌표 압축

문제 링크

문제#

수직선 위에 $N$개의 좌표 $X_1$, $X_2$, ..., $X_N$이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

$X_i$를 좌표 압축한 결과 $X'_i$의 값은 $X_i > X_j$를 만족하는 서로 다른 좌표 $X_j$의 개수와 같아야 한다.

$X_1$, $X_2$, ..., $X_N$에 좌표 압축을 적용한 결과 $X'_1$, $X'_2$, ..., $X'_N$를 출력해보자.

입력#

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 $X_1$, $X_2$, ..., $X_N$이 주어진다.

출력#

첫째 줄에 $X'_1$, $X'_2$, ..., $X'_N$을 공백 한 칸으로 구분해서 출력한다.

풀이#

값 자체의 크기는 중요하지 않고, 정렬했을 때 몇 번째로 작은 값인지가 중요하다. 그래서 중복을 제거한 뒤 정렬 순서를 새 번호로 붙이면 된다.

코드에서는 원본 배열을 하나 보관해 두고, 복사본을 정렬한 뒤 고유한 값마다 압축된 번호를 매핑한다. 이후 원본 순서대로 맵을 조회해 출력하면 된다.

결국 정렬과 매핑을 한 번 해 두면 이후 출력은 단순 조회만 남는다. 좌표 압축은 값을 줄인다기보다 순서만 남긴다고 이해하는 편이 좋다.

코드#

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
void solve() {
	int N, n;
	cin >> N;
 
	vector<int> vec, coord;
 
	for (int i = 0; i < N; i++) {
		cin >> n;
		vec.push_back(n);
		coord.push_back(n);
	}
 
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());
 
	for (int j = 0; j < N; j++) {
		cout << lower_bound(vec.begin(), vec.end(), coord[j]) - vec.begin() << " ";
	}
}
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	solve();
 
	return 0;
}

복잡도#

• 시간 복잡도: 좌표를 정렬하고 압축 값을 매핑하므로 $O(N \log N)$이다.
• 공간 복잡도: 좌표 배열과 압축 결과를 저장하므로 $O(N)$이다.

마무리#

값을 줄이는 문제가 아니라 정렬 순서의 번호만 다시 매긴다고 보면 좌표 압축이 훨씬 쉽다.