728x90
문제
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.
X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.
입력
첫째 줄에 N이 주어진다.
둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.
출력
첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.
코드
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int N;
pair<int,int> p;
vector<pair<int,int>> x;
vector<pair<int,int>> tmp;
bool compare(pair<int,int> a, pair<int,int> b){
return a.first < b.first;
}
bool compare2(pair<int,int> a, pair<int,int> b){
return a.second < b.second;
}
int main(){
cin >> N;
for(int i=0; i<N; ++i){
int a;
cin >> a;
p.first = a;
p.second = i;
x.push_back(p);
}
stable_sort(x.begin(), x.end(),compare);
tmp = x;
int num = 0;
for(int i=0; i<N; ++i){
if(i == 0){
x[i].first = num;
num++;
}
else{
if(tmp[i-1].first == tmp[i].first){
x[i].first = x[i-1].first;
}
else{
x[i].first =num;
num++;
}
}
}
stable_sort(x.begin(), x.end(), compare2);
for(int i=0; i<N; ++i){
cout << x[i].first<<' ';
}
return 0;
}
문제 자체는 굉장히 쉬워보인다. 하지만 제한사항에 N이 10^6까지 커질수 있기 때문에 함부로 했다간 큰코 다친다.
이 문제는 O(N^2)으로 풀면 시간 초과가 걸리기 때문에 sort함수를 잘 이용해야 한다.
나 같은 경우엔 stable_sort를 이용해 풀어줬지만 unique와 erase함수를 사용하면 더쉽게 풀 수 있다.
+ unique, erase를 이용한 풀이는 나중에..
728x90
반응형
'PS > 기타 알고리즘' 카테고리의 다른 글
[11478] 서로 다른 부분 문자열의 개수 (0) | 2023.02.05 |
---|---|
[1008] (C++) A/B (0) | 2022.08.28 |
[11651] (C++) 좌표 정렬하기2 (0) | 2022.08.01 |
[10814] (C++) 나이순 정렬 (0) | 2022.08.01 |
[백준 / 11650] (C++) 좌표 정렬하기 (0) | 2022.06.19 |