[백준 18870] 좌표 정렬 [C/C++]

백준 - 18870

---

풀이

입력받은 좌표들을 오름차순으로 정렬하고, 중복을 제거했을 때, 각 요소들이 몇 번째인지 출력하는 문제다.

 

입력받은 수들을 두 벡터에 저장하고, v2는 오름차순으로 정렬 후, 중복을 제거했다.

중복된 수가 제거된 v2에서 lower_bound()를 사용하면, 원하는 결과를 얻을 수 있다.

---

소스코드

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int N, temp;
    scanf("%d", &N);
    vector<int> v1(N), v2(N);
    for (int i = 0; i < N; i++){
        scanf("%d", &temp);
        v1[i] = v2[i] = temp;
    }
    sort(v2.begin(), v2.end());

    v2.resize(unique(v2.begin(), v2.end()) - v2.begin());

    for (int i = 0; i < N; i++)
        printf("%d ", lower_bound(v2.begin(), v2.end(), v1[i])-v2.begin());
}

---

출처

18870번: 좌표 압축