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

18870번: 좌표 압축

---

반응형

 

📌 접근 방법

⚡ 좌표 압축 : 해당 좌표의 값을 그 값보다 작은 좌표값들의 개수로 대체

• N 개의 숫자를 입력받고 오름차순으로 정렬해준다
• 중복을 제거해주고 뒤에 필요없는 값들은 제거 해줌 (중복제거를 한 후 벡터 앞부터 다시 채운거라 뒤에는 쓰레기 값들이 남아있음)
• lower_bound 함수를 이용해서 찾는 값보다 같거나 큰 값을 리턴해줌.

 

✔ unique(b, e)

• <algorithm> 헤더파일 사용
• vector의 begin, end을 넣어주고 "==" 연산자를 이용해 원소들이 같은지 비교
• vector 배열에서 중복되지 않는 원소들을 앞에서부터 채워나가는 함수
  • 나머지 값들(필요없는 값)은 그대로 vector 원소 값이 존재함
  • erase와 함께 자주 쓰임 (뒤에 남은 값들 제거)
• 정렬된 상태로 진행해야 함
• 시간 복잡도 O(n)

✔ lower_bound 

• 이진탐색기반.
• 해당 값보다 크거나 같은값이 제일 처음 등장하는 곳 위치를 리턴해준다

 

 

 

✅  Pass Code

#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    cin>>N;

    vector<int> v;

    for(int i=0; i<N; i++){
        int x;
        cin>>x;
        v.emplace_back(x); 
    }
    
    vector <int> tmp=v;
    sort(tmp.begin(), tmp.end()); //정렬해줌
    tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end()); // 중복을 제거하고 resize해줌

    for(auto&& x : v){
        cout<<lower_bound(tmp.begin(), tmp.end(), x)-tmp.begin()<<' '; // x보다 작은 수가 몇 개 있는지(중복 제외) 찾기위해 앞에서 중복을 제거하고 정렬된 새로운 벡터의 원소 순서를 이용해 출력
    } 
    cout<<"\n";
    return 0;
}