[백준] 18869번: 멀티버스 2 C++ 풀이 - 좌표 압축 기술과 벡터 중복 제거

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

---

먼저 문제를 꼭 읽어보고 좌표 압축은 떠올리지 말고 풀이를 생각해보자.

 

최대 100개의 우주이고 각 우주당 10000개의 행성이 존재한다. 그냥 완전 탐색을 생각해보면 총 100*100 번의 루프를 돌 것이고, 한 번의 루프에 10,000개의 행성에 대해 모든 index 쌍별로 어떤 값이 더 큰지를 계산해봐야 한다. 얼추 계산해봐도 10,000 C 2 * 10,000 ... 불가능하다. 문제가 되는 부분은 두 개의 우주에 대해 그 우주가 균등한지를 계산하는 과정이다. 이 부분만 해결하면 될 것 같다.

 

아래의 예시로 좀 더 생각해보자. 균등한 행성들이다.

2 3
3 17 5
12 50 31

 

값 3 17 5를 정렬하면 3 5 17이다. 그냥 정렬해버리면 5가 어디에 있던 행성이고 17이 몇 번째 행성인지 알 수 없다. 차라리 각 값이 몇 번째로 큰지 알면 비교하기가 더 수월할 것 같다. 그런식으로 나타내면 3 17 5는 0 2 1이 된다. 이런 과정을 압축이라 하자.

 

이번에는 균등하지 않은 행성들로 생각해보자.

2 3
3 17 5
12 50 10

3 17 5는 0 2 1, 12 50 10은 1 2 0이 된다. 압축된 결과가 일단 다르므로 당연히 불균등하다.

 

지금까지 예시로 가설을 하나 세워볼 수 있는데, 우선 압축된 다른 배열은 불균등하다. 그렇다면 압축 결과가 같다면 항상 균등할까? 

 

같은 값이 있는 경우도 생각해보자.

2 3
3 17 3
5 50 6

3 17 3 -> 1 3 1

5 50 6 -> 1 3 2

같은 값이 있어도 문제가 없다. 딱히 더 신경 쓸 부분이 없는 것 같으니 바로 구현해보자. 구현은 좌표압축의 표본을 따라가면 된다.

---

좌표압축(Coordinate Compression)은 값의 상대적인 크기 관계만 중요하고 실제 값의 크기는 중요하지 않을 때 사용하는 기법이다. 보통 다음과 같은 알고리즘으로 구현된다.

1. 압축 대상인 배열을 벡터 tmp에 복사한다.
2. tmp를 오름차순 정렬 한다.
3. 중복된 값을 제거한다.
   • 여기서 테크닉이 들어가는데, 중복 제거 구현은 `tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());` 이렇게 한 줄로 구현이 가능하다.
   • unique 함수는 중복된 값들을 가장 뒤로 미루고, 중복된 값이 시작하는 index를 반환한다.
4. 원래 배열의 각 값을 압축된 값으로 변환한다. 여기서 압축된 값이란 정렬된 벡터에서 몇 번째 위치에 있는지를 찾아서 그 위치(인덱스)를 새로운 값으로 사용하는 것이다.

문제를 예로 들어 보면, 한 우주의 행성이 [1000, 7, 50000, 7, 30] 인 경우,

1. 정렬 후: [7, 7, 30, 1000, 50000]
2. 중복 제거 후: [7, 30, 1000, 50000]
3. 압축 후: [2, 0, 3, 0, 1]이 된다. (7→0, 30→1, 1000→2, 50000→3)

다시 말하자면 좌표 압축은 상대적인 크기 관계만 중요하고 실제 값의 크기는 중요하지 않을 때 사용하면 된다.

 

다시 구현으로 돌아와보면,,, 좌표 압축 코드를 보자.

void compress(int k)
{
    vector<int> tmp(arr[k], arr[k] + m);
    sort(tmp.begin(), tmp.end());
    tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
    // arr[k] 행의 i번째 숫자에 대해 그 index i가 값이 되게끔 하면 됨.
    for (int i = 0; i < m; i++)
        arr[k][i] = lower_bound(tmp.begin(), tmp.end(), arr[k][i]) - tmp.begin();
}

배열을 생성자로 벡터를 초기화하는 방법 vector<int> tmp(arr[k], arr[k] + m); 도 모를만 하다.

unique 제거도 알아두면 좋고, index를 새로운 값으로 사용하여 압축하는 로직도 꼭 기억해두자. lower_bound(..., ..., arr[k][i])를 하게 되면 i번째 값이 몇 번째로 큰지를 알 수 있고 이를 a[k][i]로 쓰면 된다.

 

/** BS 18869 멀티버스 2 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int n, m;
int arr[102][10002];

void compress(int k)
{
    vector<int> tmp(arr[k], arr[k] + m);
    sort(tmp.begin(), tmp.end());
    tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());

    for (int i = 0; i < m; i++)
        arr[k][i] = lower_bound(tmp.begin(), tmp.end(), arr[k][i]) - tmp.begin();
}

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

    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> arr[i][j];

    // k행 좌표 압축
    for (int k = 0; k < n; k++)
        compress(k);

    int ans = 0;
    // i행, j행 비교
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            // 두 배열이 같으면 true
            int flag = true;
            for (int k = 0; k < m; k++)
            {
                if (arr[i][k] != arr[j][k])
                {
                    flag = false;
                    break;
                }
            }
            if (flag)
                ans++;
        }
    }

    cout << ans;
}