백준 18870: 좌표 압축/정렬/Unique, Vector, lower bound 함수 사용

문제

수직선 위에 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을 공백 한 칸으로 구분해서 출력한다.

---

제한

1 ≤ N ≤ 1,000,000

-109 ≤ Xi ≤ 109

---

Unique 함수

unique 함수는 연속으로 중복되는 원소를 vector의 제일 뒷 부분 쓰레기 값으로 보낸다.

즉, 중복 되지 않는 원소들 만을 앞에서 부터 채운다.

이때 주의할 점은 연속으로 중복되는 원소만을 없애기 때문에 반드기 정렬을 시행해 줘야 한다.

---

예

예를 들어 아래와 같이 정렬된 벡터 v가 있다고 쳐보자

1 2 2 3 4 4 5

unique(v.begin(), v.end())

1. 연속으로 중복 되는 값인 2, 4를 없앤다.

⇒ 1 2 3 4 5

2. 중복 되지 않은 값들을 앞에서 부터 채우며, 중복된 값이 사라져 남게 된 공간은 원본값을 유지한다.

⇒ 1 2 3 4 5 4 5

3. unique 함수는 원본이 유지 된 원소들의 첫번째 주소 값을 반환한다.

⇒ 1 2 3 4 5 4 5 (노랑이 주소 반환)

4. 최종적으로 erase 함수를 사용해 지워주면 중복 되지 않은 값들을 얻을 수 있다.

v.erase(unique(v.begin(), v.end()), v.end());
⇒ 1 2 3 4 5

---

문제 이해

⇒ 좌표 압축이란, 현재 값에서 현재 값을 현재 값보다 작은 값들의 개수로 바꿔주는 것이다.

2 4 -10 4 -9

→ -10 -9 2 4 4

⇒ 2 3 0 3 1 (-10보다 작은 수 0개, 2보다 작은 수 2개)

※ lower_bound(시작값, 종료값, 찾는값): 찾는 값보다 같거나 큰 값을 리턴해주는 함수

이때 리턴값이 iterator이므로 .begin()을 해주면 인덱스를 리턴해준다.

---

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

int main() {
    int N;
    cin >> N;

    long long tmp;
    vector<long long> v1; // 정렬 벡터
    vector<long long> v2; // 원본 벡터
    for (int i = 0; i < N; i++) {
        cin >> tmp;
        v1.push_back(tmp); //정렬
        v2.push_back(tmp);
    }
    sort(v1.begin(), v1.end());
    v1.erase(unique(v1.begin(), v1.end()), v1.end()); // 중복값 제거

    for (int i = 0; i < N; i++) {
        cout << lower_bound(v1.begin(), v1.end(), v2[i]) - v1.begin() << " ";
    }
    return 0;
}

원본과 정렬 벡터를 따로 만들어 두고 정렬벡터 정렬하고 unique함수 써서 중복값 제거해주고,

lower_bound 함수에 원본벡터를 이용해서 몇번째로 큰지 구해주면 된다.