c++ 백준 18870 좌표 압축

18870 좌표 압축

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

좌표 압축을 적용하면 해당 좌표보다 작은 좌표의 개수를 출력한다.
처음에는 2중 for문으로 각 요소마다 벡터를 순회하면서 작으면 count++해서 전체 갯수를 세었는데 입력 예시2에서와 같이 1000보다 작은 999가 여러개일 경우 중복으로 카운트되서 옳바르지 않은 풀이가 된다.

이 문제를 해결하기 위해
추가적으로 벡터를 만들어 값을 복사하고, 정렬한 후에 중복을 없앤 인덱스가 좌표 압축의 결과가 된다. 두 가지 함수를 추가적으로 배웠는데

unique: 벡터의 중복을 제거할 때 사용됨

lower_bound

#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> vec(n);

    for (int i = 0; i < n; i++)
        cin >> vec[i];

    vector<int> copy_vec = vec;
    sort(copy_vec.begin(), copy_vec.end());
    copy_vec.erase(unique(copy_vec.begin(), copy_vec.end()), copy_vec.end()); //중복 제거

    for (int i = 0; i < n; i++) {
        auto it = lower_bound(copy_vec.begin(), copy_vec.end(), vec[i]); //vec[i]원소에 해당하는 값의 iterator를 반환
        cout << it - copy_vec.begin() << " "; // 원소의 iterator값에서 vector 시작주소를 빼면 인덱스 값을 얻을 수 있음
    }
    return 0;
}