Codility Lesson12 - CommonPrimeDivisors

🔍 문제

---

 

두 배열 A와 B가 주어지고, 같은 index의 두 요소가 최대 공약수와 똑같은 인자를 가지고 있을 경우의 수를 구하는 문제이다. 

 

CommonPrimeDivisors coding task - Learn to Code - Codility

 

✏️ 풀이 - JS

---

 

Lesson의 소제목이 유클리드의 호제법이므로, 최대 공약수는 유클리드의 호제법을 이용해서 구해주었다.

 

유클리드 호제법 포스트보기 👉 유클리드 호제법(Uclidean algorithm)

 

먼저, 두 수의 최대 공약수를 구해 준 후, 각 수를 최대 공약수와의 최대 공약수를 다시 구해주면된다.

그리고 나서 각 수를 구한 최대 공약수로 나눈 후 다시 그 값과 위의 최대 공약수로 다시 최대공약수를 구해서 과정을 반복하면 된다.

그리고 나서 gcd가 1이 되었을 때 값이 1이 아니라면 그 수가 공통되지 않은 인수가 된다. 이 시점에서 이미 공통되지 않는다는 사실이 나왔으므로 이 공통되지 않은 인수 값이 소수인지 아닌지를 판별할 필요는 없다.

 

결론은 각 수의 인수가 두 수의 최대 공약수의 인수와 같다면 인수가 같은 것으로 보면된다.

 

처음에 논리를 생각하는 과정에서 공통되지 않은 인수가 소수인지 아닌지까지 판별해서 예외 처리를 하려다보니 조금 고생을 하긴했다.

 

재귀적인 코드를 말로 설명하려니 복잡한데, 문제에서 예시로 들어준 값을 넣고 코드를 따라가다보면 더 이해하기가 쉬울 것이다.

 

시간 복잡도는 O(Z * log(max(A) + max(B))**2)가 나왔다.

function solution(A, B) {
    const Z = A.length;
    let cnt = 0;

    for(let i = 0; i < Z; i++) {
        if(hasSamePrimeDiv(A[i], B[i])) {
            cnt ++;
        }
    }

    return cnt;

    function getGCD(A, B) { //최대 공약수 구하기
        if(B === 0) return A;
        return getGCD(B, A % B);
    }

    function hasSamePrimeDiv(A, B) { //같은 인수를 가지고 있는지 확인

        let gcd = getGCD(A, B);
        let gcdA = 0;
        let gcdB = 0;;


        while(gcdA !== 1) {
            gcdA = getGCD(A, gcd);
            A = A / gcdA;
        }

        while(gcdB !== 1) {
            gcdB = getGCD(B, gcd);
            B = B / gcdB;
        }

        return (A === 1 && B === 1)? true : false; //만약 값이 1이 아니라면 그 값은 공통되지 않는 인수인 것이다.
        //또한 두 수 모두 공통된 인수를 가지고 있어야 하므로 조건식을 위와 같이 적어주었다.
    }
}