좌표 압축 (feat. 백준, 18870번)

좌표 압축
https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/18870
#include <iostream>
#include <map>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int i, N, index = 0, arr[1000000];
	map<int, int> tmp;
	cin >> N;
	for (i = 0; i < N; ++i)
		cin >> arr[i], tmp[arr[i]] = 0;
	for (auto& item : tmp)
		item.second = index++;
	for (i = 0; i < N; ++i)
		printf("%d ", tmp[arr[i]]);
	return 0;
}
// *&)*@*

1. 문제에서의 조건은 "Xi > Xj를 만족하는 서로 다른 좌표의 개수" 입니다.
2. 따라서 중복을 제거해주고 기본 우선순위의 key로 정렬되는 map을 사용하였습니다.
3. 입력받은 값을 key로 사용할 경우, value는 key와 key간 순서 즉, 0부터의 오름차순 값입니다.
4. 따라서 입력받은 값에 해당되는 key의 value를 출력하면 되겠습니다.