BaekJoon 18870번: 좌표 압축(C++)

https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

풀이법

1) 두개의 배열을 만들어서 좌표를 압축하기 위해 sort 알고리즘을 두 번 반복하여 문제를 해결했다.

2) 첫번째 입력 값에 대하여, 현재의 값과 index를 담을 수 있는 배열을 만들어 현재의 값을 오름차순으로 정렬시켰다.

3) 두번쨰 배열의 경우, 오름차순 된 첫번째 배열의 크기에 맞게 index를 새로 부여하여 새롭게 만들어야 하는 좌표를 압축시킨 배열을 만들어 주었다. (이때 같은 값을 가진 원소는 같은 index를 부여 해야한다)

4) 만들어진 배열을, 입력 값에서 주어진 index와 같은 순서로 출력하기 위해 sort 해주었고 최종 결과를 출력하였다.

#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;

vector<pair<int,int>> vec;
vector<pair<int,pair<int,int>>> temp;
int n;
bool compare(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b)
{
	if (a.second.first < b.second.first)
		return true;
	else
		return false;
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		vec.push_back({ a,i });
	}
	sort(vec.begin(), vec.end());
	int index = 0;
	temp.push_back({ vec[0].first,{vec[0].second,index } });
	for (int i = 1; i < n; i++)
	{
		if (vec[i].first != temp[i - 1].first)
			index++;
		temp.push_back({ vec[i].first,{vec[i].second,index } });
	}
	sort(temp.begin(), temp.end(), compare);
	for (int i = 0; i < temp.size(); i++)
	{
		cout << temp[i].second.second << " ";
	}

}