[백준 18870] [이분탐색] [Unique/erase] 좌표 압축

이 문제를 요약하자면

1. 데이터를 받고

2. 자기보다 작은 숫자의 갯수를 출력한다.

라고 볼 수 있다.

 

즉, 이 문제를 풀기 위해서는 다음의 과정을 겪어야 한다.

1. 정렬을 한다.

2. 자기보다 작은 숫자의 갯수만 카운트 하되, 서로 다른 좌표의 갯수이므로 중복되는 것은 제거한다.

 

이때, 정렬하는 과정에서 O(nlogn)이고, erase까지 하는데 O(nlogn)가 사용된다.

추가로 자기보다 작은 숫자의 갯수를 전부 다 고려하려면 O(n^2)인데, 이 경우에는 시간 초과가 나므로 이분탐색을 활용해서 진행을 해주면

O(nlogn)이므로 충분히 2초안에 통과할 수 있음을 확인할 수 있다.

 

위의 방식을 활용하여 코드를 짜주면 다음과 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main(void){
    int n;
    cin >> n;
    vector<long long> data;
    for(int i = 0; i < n; i++){
        int value;
        cin >> value;
        data.push_back(value);
    }

    vector<long long> data_save = data;
    sort(data.begin(), data.end());
    data.erase(unique(data.begin(), data.end()), data.end());
    
    int size_of_data = data.size();

    for(int i = 0; i<n; i++){
        int start = 0;
        int end = size_of_data;
        int mid = (start + end) / 2;

        // Binary search
        while(true){
            mid = (start + end) / 2;
            if (data[mid] > data_save[i]){
                end = mid - 1;
            }
            else if(data[mid] < data_save[i]){
                start = mid + 1;
            }
            else break;
        }
        cout << mid << " ";
    }
    
    cout << "\n";

    return 0;
}

 

추가적으로 Vector container를 처음 활용해보았는데, 구글링으로 여러번 검색을 하면서 동적할당인 vector container에 익숙해지도록 노력해야겠다.

 

추가적으로 원소를 집어넣고 싶을 때는, push_back를 활용하면 된다.

 

또한, 이 문제의 상황에서 erase와 unique를 사용하였는데 사용방법은 대략적으로 다음과 같다.

(unique함수는 algorithm 헤더에 존재하고, erase는 vector container에서 사용된다.)

sort( vec.begin(), vec.end() );

vec.erase( unique( vec.begin(), vec.end() ), vec.end() );

 

정렬을 시키고 unique 및 erase를 사용해야한다는 것을 유의해야 한다.

이때, unique 함수의 time complexity는 O(nlogn)이다.

 

추가적으로 erase 함수의 사용방법은 다음과 같다.

• erase 함수는 vector 배열에서 특정 원소를 삭제하는 기능을 담당하는 함수이다.
• v.erase(v.begin()+a, v.begin()+b) 명령어를 입력하면 [a,b) 원소가 삭제된다. 즉 시작 지점은 닫힌구간, 끝나는 지점은 열린 구간으로 삭제된다.
• unique 함수를 적용한 벡터배열에서 필요한 원소만 뽑아낼 수 있다.