[백준 C++] 18870 좌표 압축 - 정렬

18870번: 좌표 압축

#include <iostream>
#include <set>
#include <unordered_map>
using namespace std;

int X[1000000];
set<int> OrderedList;
unordered_map<int, int> Map;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		cin >> X[i];
		OrderedList.emplace(X[i]);
		Map.emplace(X[i], -1);
	}

	int i = 0;
	for (const int& Number : OrderedList)
	{
		Map[Number] = i;
		++i;
	}

	for (int i = 0; i < N; ++i)
	{
		cout << Map[X[i]] << ' ';
	}
}

---

 

set의 중복 없이 자동 정렬되는 성질을 이용해서 숫자를 넣어주었습니다.

그리고 unordered_map에 각 숫자가 몇번째 순서로 정렬되었는지의 값을 저장하도록 했습니다.

 

다른 분들의 풀이를 보니 vector 하나만 사용해서 sort함수 호출해준 뒤

따로 조건을 설정해서 정렬된 순서를 count 해주는 방식으로 푸는 방법도 존재했습니다.

해당 방법이 시간 복잡도 측면에서 약 5배 정도 더 유리한 것을 확인할 수 있었습니다.