[Algorithm] Baekjoon 11870번 : 좌표 압축

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

18870번: 좌표 압축

map<int, vector<int>> m;
int arr[1000001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    int input = 0;
    int prevCount = 0;
 
    cin >> n;
 
    for (int i = 1; i <= n; i++)
    {
        cin >> input;
 
        m[input].push_back(i);
    }
 
    for (auto iter = m.begin(); iter != m.end(); ++iter)
    {
        for (int i = 0; i < iter->second.size(); i++)
        {
            arr[iter->second[i]] = prevCount;
        }
 
        prevCount += 1;
    }
 
    for (int i = 1; i <= n; i++)
    {
        cout << arr[i] << ' ';
    }
}

첫 풀이는 이렇게 했다.

통과는 했으나, 시간효율이 굉장히 좋지 않아서 다른 풀이를 보고 다시 코드를 짰다.

 

 

vector<int> v;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    int input = 0;
 
    cin >> n;
 
    for (int i = 1; i <= n; i++)
    {
        cin >> input;
        v.push_back(input);
    }
 
    vector<int> temp = v;
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
 
    for (int i = 0; i < temp.size(); i++)
    {
        cout << lower_bound(v.begin(), v.end(), temp[i]) - v.begin() << ' ';
    }
}
 

 

이제서야 좀 정상적인 시간이 나온다.

unique함수로 중복을 제거하는게 포인트다. 하나의 점에 몇개의 인덱스가 있든간에, 1개로 취급하기 때문이다.

unique함수를 쓰기 전에는 기본적으로 정렬을 해야하며, 리턴값으로 뒤의 쓰레기값들의 시작위치를 리턴한다.

그렇기 때문에 그부분을 erase로 지우는 작업까지하면 v에는 깔끔하게 중복제거된 값들만 남게된다.

그다음 다시 인풋값 받았던 원본 벡터를 돌면서 lower_bound 함수를 통해 해당 인풋값이 정렬된벡터에서 몇번째에 위치했는지를 출력해주면 된다.

 

사실 unique로 중복제거정렬까지 한 다음에, lower_bound 안쓰고 map에 체크하고 출력하는 식으로 해봤는데 N이 최대 100만개라 그런가 생각보다 시간효율이 안좋았다.

알아보니까 lower_bound가 탐색개수가 많아질수록 성능이 상당히 좋다고 한다. 

이건.. 자주 애용해야겠다.