BOJ 18869번: 멀티버스 2

문제 설명

여러 개의 우주들과 각 우주 속 행성의 크기가 주어졌을 때, 같은 패턴의 행성을 가지고 있는 우주 쌍의 개수 구하기

🔗 문제 링크

핵심 아이디어

• 각 우주는 상대적인 순서만 중요 → 좌표 압축
• 압축된 벡터를 map에 저장하여 빈도 수 계산
• 같은 벡터가 n개 있으면 쌍의 수는 n*(n-1)/2 → nC2

코드

#include <bits/stdc++.h>
using namespace std;
int m, n;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    map<vector<int>, int> freq;
    
    cin >> m >> n;
    for(int i = 0; i < m; i++){
        vector<int> x(n), sorted;
        for(int j = 0; j < n; j++){
            cin >> x[j];
            sorted.push_back(x[j]);
        }
        
        sort(sorted.begin(), sorted.end());
        sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
        
        vector<int> compressed;
        for(int j = 0; j < n; j++){
            compressed.push_back(lower_bound(sorted.begin(), sorted.end(), x[j]) - sorted.begin());
        }
        
        freq[compressed]++;
    }
    
    int ans = 0;
    for (auto& [key, cnt] : freq) {
        ans += cnt * (cnt - 1) / 2;
    }
    cout << ans;
}

‼️ 놓친 점

• map<vector, int> freq; 이런 방식으로 Map을 사용하여 같은 패턴의 벡터 찾기 가능!
• 벡터 압축 시 unique를 활용하여 중복 값 없애기
• 우주의 개수가 100개로 적기 때문에 int로도 답 저장 가능!
• cnt가 2보다 작을 경우 cnt-1에서 어차피 0으로 되기 때문에 굳이 (cnt > 2) 확인할 필요 없음