[LeetCode] 952. Largest Component Size by Common Factor

https://leetcode.com/problems/largest-component-size-by-common-factor/

Largest Component Size by Common Factor - LeetCode

Largest Component Size by Common Factor - Hard

 

수가 주어졌을때, 같은 약수를 갖고 있는 수들끼리 연결한다.

이 때, 연결되어 있는 그룹들 중 멤버수가 최대인 그룹의 멤버수를 구하는 문제다.

주의할 점은 2,18,3 을 보면 2와 3은 같은 약수가 없지만, 서로 18과 연결되어 있으므로 같은 그룹이다.

 

풀이방법 자체는 조금 삽질하다가 금방 떠올렸다.

모든 수를 소인수분해를 먼저 해주고, union find 를 이용해 소인수들끼리 연결시켜준다.

마지막으로 원래 수를 그 수를 이루는 가장 작은 소인수의 그룹에 매칭시킨 후,

그룹의 멤버수를 세어준다.

 

하지만 구현을 하는 과정이 조금 까다로웠다.

결국 구현은 했으나 지저분하고 메모리/시간 면에서 최적화되어 있지가 않다.

 

전체 풀이 코드

class Solution {
public:
    unordered_map<int, int>n,m;
    int largestComponentSize(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        unordered_map<int, vector<int>> pd;
        int M = nums.back(), ret = 0;
        int primes[100005] = {};
        for (int i=2; i<=M; i++) for (int j=2; i*j<=M; j++) primes[i*j] = 1;
        for (int num:nums) {
            n[num] = 1;
            if (num==1) pd[1] = {1};
        }
        for (int i=2; i<=M; i++) {
            if (!primes[i]) {
                m[i] = i;
                for (int j=1; i*j<=M; j++) if (n[i*j]) pd[i*j].push_back(i);
            }
        }
        for (int num:nums) {
            int pm = pd[num][0];
            for (auto prime:pd[num]) _union(pm, prime);
        }
        for (int num:nums) ret = max(ret, ++primes[find(m[pd[num][0]])]);
        return ret;
    }
    int find(int a) {
        if (m[a] == a) return a;
        return find(m[a]);
    }
    void _union(int a, int b) {
        int ma = find(a);
        int mb = find(b);
        if (ma<mb) m[mb] = ma;
        else m[ma] = mb;
    }
};