[BOJ/C++]18870번_좌표 압축

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

 

##문제 풀기 전 내가 알고 있었어야 할 개념:

1_ Vector 상에서 중복제거 후, 재정렬 방법 :

   1_1) Sort로 오름차순 (or 내림차순) 정렬

   1_2) auto last = unique(V.begin(), V.end());

=> Vector V에서 중복을 제거한 배열로 시작하여 정렬하고, 중복된 요소들은 뒤로 재껴준다. (중복된 것이 몇개 있는지는 안정 보장 x)

ex_ V = {3,2,4,5,5,6,1,2}  ====> V = {1,2,3,4,5, 6 ,/ last지정 iterlator 시작부분,,... }

   1_3) last 부터 끝까지 (중복된 요소들이 있는 범위) 삭제

=> V.erase(last,V.end());

2★_ 원래 요소와 변형 후, 배열(or Vector)  요소 비교하기 => 이분탐색(Binary Search) [C언어로 공부 따로 할 필요있음]

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
 
int main() {
    init();
 
    int N;
    cin >> N;
 
    vector<int> arr(N);     // 정렬할 배열
    vector<int> arr_2(N);   // 원본 배열을 복사할 배열
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];  // 배열 입력
        arr_2[i] = arr[i];  // 배열 복사
    }
 
    // 정렬
    sort(arr.begin(), arr.end());
 
    // 중복 제거
    auto last = unique(arr.begin(), arr.end());
    arr.erase(last, arr.end());
 
    // 인덱스를 찾기 위해 원본 배열의 각 원소에 대해 이진 탐색 수행
    for (int i = 0; i < N; i++) {
        // lower_bound를 사용하여 원소의 위치를 찾음
        auto it = lower_bound(arr.begin(), arr.end(), arr_2[i]);
        cout << (it - arr.begin()) << ' ';  // 원본 배열에서의 인덱스 출력
    }
 
    return 0;
}