https://www.acmicpc.net/problem/18870
18870번: 좌표 압축
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에
www.acmicpc.net
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(vector<int> &v1, vector<int> &v2)
{
return v1[1] < v2[1];
}
int main()
{
int N;
cin >> N;
vector<vector<int>> pos;
vector<vector<int>> pos_compressed;
for (int i = 0; i < N; i++)
{
int num;
cin >> num;
vector<int> tmp;
tmp.push_back(num);
tmp.push_back(i);
pos.push_back(tmp);
}
pos_compressed.resize(pos.size());
copy(pos.begin(), pos.end(), pos_compressed.begin());
sort(pos.begin(), pos.end());
sort(pos_compressed.begin(), pos_compressed.end());
int count = 0;
pos_compressed[0][0] = count;
for (int i = 1; i < N; i++)
{
if (pos[i - 1][0] != pos_compressed[i][0])
count++;
pos_compressed[i][0] = count;
}
sort(pos_compressed.begin(), pos_compressed.end(), cmp);
for (int i = 0; i < N; i++)
cout << pos_compressed[i][0] << ' ';
}