https://www.acmicpc.net/problem/18870
문제
> 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
> Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.
> X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.
접근
벡터를 입력받고 똑같은 벡터를 하나 더 복제해준 뒤
이 벡터를 오름차순 정렬해주고 중복을 제거해준다.
이제 lower_bound를 사용해서 원래 벡터의 인덱스 순서대로 복제&중복제거된 벡터에서 탐색을 한다.
똑같은 벡터를 복제한것이므로 무조건 iterator를 반환한다.
반환된 값은 찾으려는 값 이상의 값이 시작되는 위치 이므로 이 위치보다 전에 있는 값들은 문제에서 원하는 작은 값들을 만족한다.
따라서 lower_bound로 반환된 값은 iterator므로 원벡터.begin()을 빼주어 정수형으로 만들어주고 이를 출력한다.
문제해결
> 원 벡터 cdn을 입력받는다. 복제 벡터 cdn2를 만들어준다.
> 정렬을 해주고, unique로 중복값을 뒤로 몰아주고 중복된 값이 시작되는 위치를 반환해 이를 시작점으로 erase를 써서 cdn2.end까지 지워준다.
> 결과를 담을 결과벡터를 하나 만들고 원 벡터의 원소 수만큼 반복을 돌려 좌표압축을 한다.
> lower_bound로 찾고자 하는 값의 시작점을 찾고 cdn2.begin()을 빼주면 작은 값들의 개수가 된다.
> 최종결과가 담긴 벡터를 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
vector<int> cdn(N);
for (int i = 0; i < N; i++) cin >> cdn[i];
vector<int> cdn2 = cdn;
sort(cdn2.begin(), cdn2.end());
cdn2.erase(unique(cdn2.begin(), cdn2.end()), cdn2.end());
vector<int> rst(N);
for (int i = 0; i < N; i++)
{
rst[i] = lower_bound(cdn2.begin(), cdn2.end(), cdn[i]) - cdn2.begin();
}
for (auto& a : rst) cout << a << " ";
}
후기
예제 입력1번만 입력했는데 정답이 나와 제출했더니 틀렸다. 혹시 해서 예제입력2번을 넣었는데 3 0 3 0 3 0이 나왔다.
생각해보니 정렬하면 999 999 999 1000 1000 1000이 되는데
1000 입장에선 작은게 3개가 있는거였다. 따라서 중복제거를 해줬다.
unique를 사용해 중복된 값을 전부 뒤로 몰아놓고 그 시작 위치를 반환한다고 한다. 이 반환값을 시작점으로 잡아 erase를 사용해 end까지하면 중복제거 로직이다.
벡터의 새로운 기능을 배웠다.
