[BOJ] 18870 : 좌표 압축 - map / pair / unique&erase 각각을 활용한 풀이 / C++

최근 map, pair, unique와 erase, 그리고 사용자 지정 정렬에 대해 배웠다.

이번 18870번 : 좌표 압축 문제가 해당 개념들을 활용하기 좋은 문제 같아, 해당 개념 및 문제에서의 활용법을 정리해보고자 한다.

 

문제

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

18870번: 좌표 압축

 

아이디어  1 : map

일단 map 형태가 가장 먼저 떠올랐다. key - value 형태로 이루어져 있는 map 형태는 key값에 따라 자동으로 오름차순 정렬된다. 또한, key값은 중복을 허용하지 않는다는 특징이 있다.

때문에, key값으로는 입력된 좌표값을, value값으로는 나중에 모든 값이 입력된 후에, map의 특정 원소가 몇 번째의 순서인지에 대한 정보를 입력해 주면 된다고 생각했다.

 

코드 : map

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

int n;
vector<int> v;
// 입력값을 그대로 담을 벡터 v 선언.
map<int, int> m;
// key값에 따라 자동으로 정렬되고 또한 중복을 허용하지 않는 map, m 선언.
//  -> 때문에 입력값을 m에 저장해 주고, 이후 value로는 index정보를 이용하면 된다.

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

    cin >> n;
    for (int i{0}; i < n; i++)
    {
        int pos;
        cin >> pos;

        v.push_back(pos);
        m.insert({pos, 0});
    }

    int i{0}; // 현재 m 상에서의 순서를 나타내는 변수 i 선언.
    for (auto &at : m)
        at.second = i++;
    // m 내부 원소들의 value값은 해당 원소의 순서이고, 이를 i를 통해 설정.

    for (auto i : v)
        cout << m[i] << " ";
        // 이후 기존에 입력값을 그대로 저장했던 v를 key값으로 m에 접근, value값을 출력해 준다.

    return 0;
}

핵심 : map

1) map은 key와 value로 구성됨. key값은 고유하며,
이 key값을 기준으로 원소들은 자동 오름차순 정렬이 됨.

2) for문에서는 range-based loop 그리고 iterator를 이용한 원소 접근 가능.
이때 iterator의 경우에는 -> 로 접근.
map[key] = value; 의 형태로도 접근할 수 있음.

 

깨달은 점

range-based for문을 통해서 map 구조를 돌 때, 처음에는 &at가 아닌 at로 second값을 변경하고자 하였다. 당연하게도 변경되지 않았는데, 후자의 경우 값을 직접 참조하는 것이 아닌 복사하는 형태이기 때문이다. 주의해 주자.

 

---

아이디어 2 : pair

일단 <입력된 값, 입력된 순서>로 구성된 pair를 담는 벡터를 선언해 주었다.

이후, 벡터를 입력된 값 기준으로 정렬해 준다.

다음으로 정렬된 벡터에서 각 pair의 first값을 압축된 값으로 교체해 준다.

-> 만약 특정 원소의 first값이 이전 원소의 first값과 다르다면

-> 이전 원소의 first값을 그 전보다 1 증가시켜 입력해 주고,

-> 값이 같다면 그 전과 동일하게 first값을 입력해 준다.

이후에 처음 입력된 순서대로 압축된 값을 출력해주어야 하므로, 이번에는 값이 입력된 순서를 기준으로 정렬해 준다.

 

이 방법은 처음에는 생각하지 못했었다. 이 문제에 많은 시간을 쏟으면서 알게 된 방법인데, pair를 정렬할 때 내가 정의한 함수를 sort에 넣어 직접 원하는 형태로 정렬을 수행할 수 있다는 사실을 알게 되어서 정리해볼 겸 풀이를 작성해보고자 했다.

 

 

코드: pair

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

int n;
vector<pair<int, int>> v;

bool compare(pair<int, int> p1, pair<int, int> p2) 
// 넘겨받는 인자의 형태 작성. 해당 코드에서는 두 pair를 넘겨받으므로 각각 p1, p2라고 정의해 주었음.
{
    return p1.second < p2.second;
    // 각 pair의 second 원소만으로 오름차순 정렬 수행.
}

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

    cin >> n;
    for (int i{0}; i < n; i++)
    {
        int a;
        cin >> a;
        v.push_back({a, i}); // pair의 first => 입력된 값 , second => 입력된 순서
    }

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

    int pressedCoordinate{0}; // 각 pair의 first값(입력받은 값)을 압축된 좌표값으로 대체할 변수 선언.
    for (int i{1}; i < n; i++)
    {
        if (v[i - 1].first != v[i].first) // 만약 특정 원소가 이전 원소와 다르다면 압축된 좌표값이 1 증가해야 함.
            v[i - 1].first = pressedCoordinate++;
        else // 특정 원소가 이전 원소와 같다면, 동일하게 압축된 좌표값을 가져야 함.
            v[i - 1].first = pressedCoordinate;
    }
    v[n - 1].first = pressedCoordinate;
    // 두 원소의 값 비교에서 앞 원소만을 변경해 왔으므로, 벡터의 마지막 pair도 설정해 주어야 함.

    sort(v.begin(), v.end(), compare);
    // 두 번째 원소만으로 정렬하기 위해, 직접 정의한 함수 compare를 세 번째 인자로 넘겨 줌.

    for (auto p : v)
        cout << p.first << " ";
}

 

핵심 : sort를 통한 사용자 정의 정렬

sort의 세 번째 인자로 우리가 정의한 함수를 넣어줄 수 있다.
이 함수는 반드시 true 혹은 false를 리턴하는 bool형태의 함수여야 한다.
예를 들어 넘겨받는 두 값 tuple<a1,b1,c1>과 tuple<a2,b2,c2>을 이용한다고 했을 때,
return b1<b2; 작성 시 오직 b1과 b2만을 기준으로 오름차순 정렬을,
return c1>c2; 작성 시 오직 c1과 c2만을 기준으로 내림차순 정렬을 수행하게 된다.

 

---

풀이3 : unique & erase

unique함수와 erase함수의 존재는 문제를 풀고 난 뒤 알게 되었다.

unique함수는 넘겨받은 범위 내의 중복되는 값들을 뒤로 보낸 후, 뒤로 보내진 첫 번째 원소의 iterator를 리턴한다.

(ex : 1 2 3 1 1 1 2 3 3 -> 1 2 3 1 2 3 / 1 1 3, 이후 첫번째 1에 해당하는 iterator 반환)

위의 특성 때문에 unique함수만 사용할 경우 뒤로 보내진 의미없는 값들까지 남아있게 되므로, 이를 주어진 범위 내의 원소들을 모두 지워 주는 erase함수와 같이 사용하면 원하는 결과를 얻을 수 있다. unique함수의 리턴값은, 필요없는 원소의 시작점이므로, erase함수의 첫 번째 인자로 unique함수를 사용하고 두 번째 인자로 배열의 끝부분을 선언해주면 될 것이다.

 

풀이 : unique & erase

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

int n;
vector<int> v; // 원본 벡터

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

    cin >> n;
    v.resize(n);
    for (int i{0}; i < n; i++)
        cin >> v[i];
    vector<int> cpv = v; // 원본을 복사하여, 정렬 및 중복된 수를 없애줄 벡터
    sort(cpv.begin(), cpv.end());

    cpv.erase(unique(cpv.begin(), cpv.end()), cpv.end());
    // unique함수의 리턴값인 첫 번째 중복 원소 -> 마지막 원소까지 지워줌으로써 중복 제거.

    for (int i{0}; i < n; i++)
        cout << lower_bound(cpv.begin(), cpv.end(), v[i]) - cpv.begin() << ' ';
    // lower_bound를 통해 찾는 값의 iterator를 얻은 후, 이를 첫 번째 원소의 iterator로 빼 주면 된다.
}

 

핵심 : erase & unique 함수와 lower_bound 함수

앞서 설명한 erase와 unique함수 말고도 문제 풀이에 큰 기여를 한
핵심적인 개념이 있는데, 바로 lower_bound 함수이다.

lower_bound 함수는 주어진 범위 내에서
찾는 원소보다 크거나 같은 값을 첫 번째로 가지는 원소의 iterator를 리턴한다.

upper_bound는 찾는 원소 이상의 값이 아닌,
찾는 원소보다 큰 값을 찾는다는 점 말고는 동일하다.

위 두 함수는 이진 탐색을 이용하기 때문에,
배열이 정렬되어 있기만 한다면 find 함수 대신
이 함수들을 이용하는 것이 더욱 빠를 것이다.
처음에는 lower_bound 함수 대신 find함수를 이용했다가
시간 초과가 떠서 많이 당황했었다.