18869. 멀티버스 Ⅱ

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

18869번: 멀티버스 Ⅱ

 

풀이

필요 지식: 이분탐색, 좌표 압축

 

두 우주 각각에 존재하는 행성들의 크기가 동일한 대소 관계를 가질 경우, 두 우주가 균등하다고 정의하고 있다. 즉, 우주 A의 세 행성들의 크기가 (행성 1) < (행성 2) = (행성 3)이면, 우주 B의 세 행성도 (행성 1) < (행성 2) = (행성 3)이어야 한다는 뜻이다.

 

우주가 최대 100개, 행성이 최대 1만 개이므로 총 비교해야 할 행성의 개수는 100만 개. 이 행성들의 크기를 일일이 비교하는 짓은 매우 비효율적이고 시간도 오래 걸린다. 우리한테 필요한 것은 행성의 크기가 아닌 행성의 대소 관계이므로, 좌표 압축을 통해 이를 최적화하여 나타낼 수 있다.

 

좌표 압축이 무엇인지는 이 문제를 풀면서 익히길 바란다. 압축 과정에서 효율적인 값의 크기 판단을 위해 이분탐색이 동반되니 이 부분에 대한 지식도 필요하다. 핵심은 어느 행성이 있을 때, 그 행성보다 작은 행성이 얼마나 있는지를 나타낸다는 것이다. 가령 어느 우주의 행성 크기가 {5, 2, 3, 6, 3}일 때, 각 행성보다 작은 행성이 몇 개인지를 나타내도록 좌표 압축하면 {3, 0, 1, 4, 1}이다. 행성의 절대적인 크기가 아닌 상대적인 크기를 나타내는 셈이므로, 균등한 우주를 판단할 때는 좌표 압축된 행성의 크기가 서로 같은지만 확인하면 된다.

 

시간 복잡도

C++ intro sort의 시간 복잡도는 \(O(N\log{N})\), std::unique의 시간 복잡도는 \(O(N)\), std::lower_bound의 시간 복잡도는 \(O(\log{N})\)이다. \(M\)개의 각 우주마다 정렬 후 중복 제거 및 \(N\)번의 lower_bound 함수를 사용하여 좌표 압축하고, 이중 for문으로 균등한 우주인지를 확인하므로 총 시간 복잡도는 \(O(M(N\log{N}+N+N\log{N})+M^{2}N)=O(MN(2\log{N}+1+M))\simeq O(MN(M+\log{N}))\)이다.

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;

int M, N, ans;
int space[100][10000];
int sorted[100][10000];

// 두 우주가 균등한지 확인하는 함수
bool equalSpace(int n1, int n2) {
    for(int i = 0; i < N; i++) {
        if(space[n1][i] != space[n2][i]) return false;
    }

    return true;
}

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

    cin >> M >> N;
    for(int i = 0; i < M; i++) {
        for(int j = 0; j < N; j++) {
            cin >> space[i][j];
            sorted[i][j] = space[i][j];
        }
    }
    
    // 좌표 압축
    for(int i = 0; i < M; i++) {
        sort(sorted[i], sorted[i] + N);
        unique(sorted[i], sorted[i] + N);
        for(int j = 0; j < N; j++) {
            space[i][j] = lower_bound(sorted[i], sorted[i] + N, space[i][j]) - sorted[i];
        }
    }

    for(int i = 0; i < M - 1; i++) {
        for(int j = i + 1; j < M; j++) {
            if(equalSpace(i, j)) ans++;
        }
    }

    cout << ans;
    return 0;
}