백준 18870 ( C++ )

좌표 압축

 

주어진 좌표의 크기 순위를 출력하면 되는 문제

 

 

문제 풀이

 

1. 좌표의 개수 n을 입력받고 길이가 n인 벡터 2개를 준비한다

 

2. 벡터 1개를 정렬한다

 

3. 정렬한 벡터의 중복 값을 모두 제거한다

 

4. 원본 벡터의 원소들을 선형으로 하나씩 참조하여 참조한 원소들이 정렬한 벡터에서는 몇 번째 인덱스에 위치하는지 찾아서 출력해준다

 

 

추가 설명

 

• 좌표값을 읽어 저장할때 벡터의 push_back 메소드를 이용하는 것보다는 벡터의 길이를 n으로 먼저 선언하고 인덱스 값을 참조하며 좌표를 저장하는 것이 더 빠르다.
• 벡터에서 중복값을 지울 때는 벡터의 erase와 unique 메소드를 이용한다.
• 원소 값을 벡터에서 찾을 때는 선형으로 찾지 말고 이진 탐색(binary search)같이 탐색 속도가 더 빠른 알고리즘으로 탐색한다.
• "ios_base::sync_with_stdio(false);" , "cin.tie(NULL);" 코드로 데이터를 읽어 들이는 속도를 더 빠르게 할 수 있다

---

코드

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int b_search(vector<int> & v, int x) {
 
 
    int l = 0 , r = v.size() - 1;
 
    int mid = 0;
   
    while ( l <= r ) {
   
        mid = ( l + r ) / 2;
 
        if ( v[mid] < x ) {
            l = mid + 1;
        }
        else if ( v[mid] > x ) {
            r = mid - 1;
        }
        else
            return mid;
 
    }
 
return -1;
}
 
 
int main (void) {
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int n;
    cin >> n;
 
    vector<int> v(n);
    vector<int> plain_v(n);
 
    int temp = 0;
 
    for (int i = 0; i < n ; i++ ) {
        cin >> temp;
        v[i] = temp;
        plain_v[i] = temp;
    }
 
    sort(v.begin(), v.end());
 
    v.erase(unique(v.begin(), v.end()), v.end());
 
 
    for (int i = 0; i < n ; i++ ) {
        int x = plain_v[i];
 
        cout << b_search(v, x) << " ";
 
    }
 
    return 0;
}