문제

백준 18870번 - 좌표 압축

코드

#include <bits/stdc++.h>
#include "unordered_map"
using namespace std;

int N;
vector<int> v1;
unordered_map<int, int> m;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        int input; cin >> input;
        v1.push_back(input);
    }

    vector<int> v2(v1);
    sort(v2.begin(), v2.end());
    v2.erase(unique(v2.begin(), v2.end()), v2.end());

    int size = v2.size();
    for (int i = 0; i < size; i++)
    {
        m[v2[i]] = i;
    }

    for (int i = 0; i < N; i++)
    {
        cout << m[v1[i]] << ' ';
    }
    
    return 0;
}

풀이

어떤 1차원 배열에서 i번째 인덱스의 X 값보다 작은 값들의 개수를 구해야 한다

예제로 배열 2 4 -10 4 -9이 있을 때
배열 내에서 2보다 작은 서로 다른 값은 -10, -9가 있으니
좌표 압축으로 만들어진 값은 2

4보다 작은 값은 2, -10, -9니까 좌표 압축하면 3.. 이런 식으로

여기서 한 가지 신경써야 할 점은 서로 다른 값이라는 것이다. 문제의 2번째 예시를 보면 100과 99만 있어서 100은 좌표 압축하면 1, 99는 좌표 압축하면 0이 나온다

이제 문제 풀이 방식을 생각해보자

N이 1,000,000까지니까 이중 반복문은 절대 안된다. 그래서 내가 선택한 방법은 입력 받은 벡터를 그대로 두고 새로운 벡터를 만든다

그 후 오름차순으로 정렬한 뒤 erase와 unique를 통해 중복된 값들을 모두 제거한다

그렇게 만들어진 배열의 요소들의 인덱스는 배열 내에서 그 요소보다 작은 개수가 된다

이제 새로 만든 배열을 순회하면서 map에 넣어주고 원래 배열을 순회하며 데이터를 꺼내면 끝

찾아보니까 map말고 lower_bound 쓰는 방법도 있었네 이걸 까먹었다