[BaekJoon] 18870번 좌표압축

• 이 글은 C++로 풀이를 작성하였습니다.

문제

 

예시

---

풀이

• 처음 생각했을 때 정렬 후 map을 통해 중복제거하고 값을 key로 0부터 하나씩 담기는 count를 value로 하여 추가한 풀이를 작성하였습니다. 이렇게 하면 map은 insert의 시간복잡도는 O(logN), 이후 정렬에 대한 시간복잡도 O(NlogN)이 걸려 전체 수에 대해서 탐색할 때의 시간복잡도는 O(N2logN)입니다.
• 다음 풀이는 무조건 시간초과가 나타나게 되는데 map이 아닌 unordered_map을 사용하면 이진 검색 트리가 아닌 해쉬 테이블로 구현이 되어 O(1)만에 통과할 수 있습니다.

#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;

int main(){
    int arr[1000005];
    int vec[1000005];
    int num;
    cin>>num;

    for(int i=0;i<num;i++){
        cin>>arr[i];
        vec[i] = arr[i];
    }

    sort(arr, arr+num);

    int idx = 0;
    unordered_map<int,int> m;
    for(int i=0;i<num;i++){
        if(m.count(arr[i]) == 0){
            m.insert({arr[i],idx++});
        }
    }

    for(int i = 0;i<num;i++){
        cout<<m[vec[i]]<<' ';
    }

}

• 이 풀이가 아닌 이분탐색으로도 풀 수 있습니다. 비슷하게 정렬한 후 중복을 제거합니다. 이후 lower_bound 함수를 통해 이분탐색으로 해당 인덱스를 구하면 됩니다.

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

int main(){
    int num;
    cin>>num;

    int origin[1000000];
    vector<int> v;
    vector<int> vec;
    for(int i=0;i<num;i++){
        cin>>origin[i];
        v.push_back(origin[i]);
    }

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

    int s = v[0];
    int idx = 0;
    vec.push_back(s);

    for(int i=1;i<num;i++){
        if(v[i] != s){
            vec.push_back(v[i]);
            s = v[i];
        }
    }

    for(int i=0;i<num;i++){
        cout<<lower_bound(vec.begin(), vec.end(), origin[i]) - vec.begin()<<' ';
    }

}

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.