Programmers : 숫자 카드 나누기

풀이요약

유클리드 호제법

풀이상세

1. 철수와 영희가 가진 카드의 최대공약수를 구해서, 상대방 카드에서 나누어지는지 구한다.

2. 다음과정에서 나올 수 있는 경우의 수는 총 4가지 이다.

   • 철수 및 영희의 최대공약수 모두 상대방의 카드들로 나누어지지 않는 경우 → 두 최대 공약수 중 큰 값을 반환
   • 철수의 최대공약수가 영희의 카드들로 나누어 떨어지지 않는 경우 → 철수의 최대공약수를 반환
   • 영희의 최대공약수가 영희의 카드들로 나누어 떨어지지 않는 경우 → 영희의 최대공약수를 반환
   • 둘다 나누어 떨어지는 경우 → 0 을 반환

function gcd(a,b) {
    return b ? gcd(b,a%b) : a;
}

function check(num, arr) {
    for(let i=0; i<arr.length; i++) 
        if(arr[i]%num == 0) return false;
    return true;
}

function solution(arrayA, arrayB) {
    let answer = 0;
    let [resultA, resultB] = [-1,-1];

    [resultA, resultB] = [arrayA[0],arrayB[0]];
    for(let i=1; i<arrayA.length; i++) 
        [resultA,resultB] = [gcd(resultA, arrayA[i]),gcd(resultB, arrayB[i])];
    
    const [a_check, b_check] = [resultA == 1 ? false : check(resultA, arrayB), resultB == 1 ? false : check(resultB, arrayA)];
    return a_check && b_check ? Math.max(resultA, resultB) : a_check ? resultA : b_check ? resultB : 0;
}