Lesson 12. Euclidean algorithm - CommonPrimeDivisors #3 (개선-2)

1. 속도 개선 아이디어

최대공약수를 이용하면 예외처리를 추가할 수 있다.

(최대공약수 = 1 = 서로소)

 

2. 코드 (C++)

#include <cmath>
#include <map>

//최대공약수 구하기
int GetCGD(int a, int b)
{
    if(a % b == 0) return b;
    else return GetCGD(b, a % b);
}

//소인수 구하기
map<int, int> GetPrimeDivisors(int n)
{
    map<int, int> prime_divisors = {}; //map<base, exponent>

    int i = 2;
    while(i <= n)
    {
        if(n % i == 0) // i는 소인수
        {
            auto it = prime_divisors.find(i);
            if(it == prime_divisors.end())
            {
                prime_divisors.insert(pair<int, int>(i, 1));
            }
            else
            {
                it->second += 1;
            }

            // n을 i로 나누어서, n 값을 줄인다
            // 소인수 i가 여러번 쓰일수도 있기 때문에, i값을 증가시키면 안된다.
            n /= i;
        }
        else //i는 n의 소인수가 아니다
        {
            i++;
        }
    }

    return prime_divisors;
}

int solution(vector<int> &A, vector<int> &B) {

    int cnt = 0;

    for(size_t i = 0; i < A.size(); i++)
    {
        //예외처리
        if(A[i] == B[i])
        {
            cnt++;
            continue;
        }
        
        int gcd = GetCGD(A[i], B[i]);
        if(gcd <= 1) continue; // 최대공약수가 1이면, 서로소

        //A[i], B[i], 소인수 구하기
        map<int, int> div_a = GetPrimeDivisors(A[i]);
        map<int, int> div_b = GetPrimeDivisors(B[i]);

        //예외처리, 개수가 같지 않으면 소인수의 밑이 같을 수 없다
        if(div_a.size() != div_b.size()) continue;
        
        bool same = true;
        auto it_a = div_a.begin();
        auto it_b = div_b.begin();
        while(it_a != div_a.end() && it_b != div_b.end())
        {
            if(it_a->first != it_b->first)
            {
                same = false;
                break;
            }
            
            it_a++;
            it_b++;
        }

        if(same) cnt++;
    }

    return cnt;
}

 

3. 결과