[백준] 18870 좌표 압축 with C++

문제설명

---

입출력 예제

---

개념

　좌표 압축은 주로 좌표 알고리즘에서 사용되는 기법 중 하나로, 입력으로 받은 좌표 값들을 작은 범위의 정수로 압축하는 것이다. 이를 사용하면 좌표 값이 매우 크거나 작은 경우에도 작은 범위의 정수로 압축해서 사용할 수 있어서, 메모리 사용량과 연산 시간을 줄일 수 있다. 예를 들어, 입력으로 10^5개의 좌표 값이 주어졌을 때, 이 값들이 10^9 이상의 큰 수라면, 메모리를 많이 사용하게 된다. 하지만 좌표 압축 개념을 사용하면, 이 값을 10^5 이하의 작은 수로 압축해서 사용할 수 있다. 

 

　문제를 푸는 데 핵심적인 요소는, 입력으로 받은 좌표 값들을 정렬해서 작은 값부터 차례대로 번호를 매길 수 있다는 것이다. 이때 각 값의 번호는 정렬된 배열에서의 인덱스 값과 일치하는데, 이 인덱스 값을 저장하는 배열을 만들어서 각 좌표 값에 해당하는 인덱스 값을 찾아 출력하면 문제를 해결할 수 있다.

---

풀이

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

int main()
{
    int N;
    std::cin >> N;
    std::vector<int> v(N);

    for (int i = 0; i < N; ++i)
    {
        std::cin >> v[i];
    }

　좌표의 개수를 N으로 초기화하고, N개의 원소를 갖는 벡터 v를 초기화해준다. 

 

    std::vector<int> ans(v);
    std::sort(ans.begin(), ans.end());
    ans.erase(std::unique(ans.begin(), ans.end()), ans.end());

　정렬된 결과를 저장할 벡터 ans를 초기화하고, 중복된 값을 지우고 정렬해준다.

 

    for (const auto& val : v)
    {
        auto it = std::lower_bound(ans.begin(), ans.end(), val);
        std::cout << std::distance(ans.begin(), it) << ' ';
    }
}

　std::lower_bound()와 std::distance() 함수를 이용해 특정 값이 몇 번째 위치에 있는지 출력하면 된다. 여기서 새로운 함수가 등장한다.

 

출처: https://en.cppreference.com/w/cpp/algorithm/lower_bound

 

　std::lower_bound() 함수는 정렬된 원소에 이진 탐색을 적용하여, 특정 값 이상이 처음 나타나는 위치를 탐색하여 위치를 반환한다. 여기서 특정 값을 찾아낸다는 점에서 'find() 함수를 쓰면 되지 않을까라는 생각'을 하고 적용했었는데, find() 함수는 선형 탐색 방식을 사용하므로 시간 초과가 발생하였다. 

 

출처: https://en.cppreference.com/w/cpp/iterator/distance

 

　std::distance() 함수는 원소 사이의 거리를 반환하는 함수다. 즉, 해당 문제에서는 정렬된 원소의 시작점 ans.begin()과 lower_bound() 함수를 이용해 찾은 원소 사이의 거리를 반환해주고 있다. 즉, distance() 함수를 이용하면 it이 가리키는 값이 ans 벡터에서 몇 번째 인덱스인지 계산할 수 있게 해 준다.

총합본

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

int main()
{
    int N;
    std::cin >> N;
    std::vector<int> v(N);

    for (int i = 0; i < N; ++i)
    {
        std::cin >> v[i];
    }

    std::vector<int> ans(v);
    std::sort(ans.begin(), ans.end());
    ans.erase(std::unique(ans.begin(), ans.end()), ans.end());

    for (const auto& val : v)
    {
        auto it = std::find(ans.begin(), ans.end(), val);
        std::cout << std::distance(ans.begin(), it) << ' ';
    }
}