백준 18869번: 멀티버스 II (C++)

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

18869번: 멀티버스 Ⅱ

---

Solved By: Coordinate Compression

 

여러 개의 우주 중 두 우주 쌍을 골랐을 때, 각 인덱스의 해당하는 두 행성의 크기의 순서가 같으면 cnt를 합니다. 모든 우주의 행성의 크기는 제각각이고, 한 우주 안에서 행성들의 크기 순서를 구해야 하기 때문에 Coordinate Compression을 사용하여 문제를 풀었습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 100
using namespace std;

int n, m;
vector<int> arr[MAX];
vector<int> temp[MAX];

int main(){
    cin >> m >> n;
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            int v; cin >> v;
            arr[i].push_back(v);
            temp[i].push_back(v);
        }
    }
    
    // coordinate-compression
    for(int i = 0; i < m; i++){
        sort(temp[i].begin(), temp[i].end());
        temp[i].erase(unique(temp[i].begin(), temp[i].end()), temp[i].end());
    }
    
    for(int i = 0; i < m; i++){
        for(int j = 0; j < arr[i].size(); j++){
            int idx = lower_bound(temp[i].begin(), temp[i].end(), arr[i][j]) - temp[i].begin();
            arr[i][j] = idx;
        }
    }
    
    int cnt = 0;
    // Brute-Force
    for(int i = 0; i < m; i++){
        for(int j = i + 1; j < m; j++){
            bool flag = 1;
            for(int k = 0; k < arr[i].size(); k++){
                if(arr[i][k] != arr[j][k]){
                    flag = 0;
                    break;
                }
            }
            if(flag) cnt++;
        }
    }
    
    cout << cnt;
    return 0;
}