BOJ18870 좌표 압축
문제
수직선 위에 N개의 좌표 X1, X2, …, XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X’i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.
X1, X2, …, XN에 좌표 압축을 적용한 결과 X’1, X’2, …, X’N를 출력해보자.
접근방식 1 (구조체)
구조체배열에 value와 index를 저장한 후, value값만 비교해서 정렬을 한다.
그 다음엔 앞의 수와 비교해서 정렬한 index 값을 value에 넣는다.
마지막으로 배열의 index값만 비교해서 처음과 같은 상태로 만든 후, index에 맞게 출력한다.
#include <bits/stdc++.h>
using namespace std;
struct y{
int i,v;
};
bool cmpv(const y&a,const y&b){
if(a.v<b.v)return true;
return false;
}
bool cmpi(const y&a,const y&b){
if(a.i<b.i)return true;
return false;
}
int main(){
ios_base::sync_with_stdio(false);
cout.tie(NULL);
int n,m=0;
y x;
vector<y> a;
cin >> n;
for(int i=0; i<n; i++){
cin >> x.v;
x.i=i;
a.push_back(x);
}sort(a.begin(),a.end(),cmpv);
for(int i=0; i<n; i++){
if(a[i].v==a[i+1].v)a[i].v=m;
else a[i].v=m++;
}sort(a.begin(),a.end(),cmpi);
for(auto i : a)cout << i.v << ' ';
}