[프로그래머스 / JavaScript] 숫자 카드 나누기

출처: https://school.programmers.co.kr/learn/courses/30/lessons/135807

✅ 문제 설명

❌ 처음 풀이

function solution(arrayA, arrayB) {
    let tmp = 0;

    for (let i = arrayA[arrayA.length-1]; i > 0; i--) {
        let flag = true;

        arrayA.forEach(num => {
            if (num % i !== 0) {  
                flag = false;
            }
        });
        
        arrayB.forEach(num => {
            if(num % i === 0){
                flag = false
            }
        })

        if (flag) { 
            tmp = i;
            break;  
        }
    }
    return tmp
}

flag를 만들어두고 arrayA에서 가장 큰 값부터 arrayA를 다 나누고 전부 나누어 떨어지고, arrayB를 다 나누고 전부 나누어 떨어지지 않으면 그대로 해당 값을 return 하는 방식으로 처음에 풀고 제출했다. 해당 방식은 최악의 경우에 arrayA의 모든 값을 거쳐갈 수 있기 때문에 시간초과가 발생해서 틀렸다.

✅ 해결

우선 arrayA에서 모든 값을 다 꺼내서 반복하는 곳에서 비효율적이라 생각하여 그 부분을 개선하려고 했다. 결국 최대 공약수가 필요하기 때문에 반복문을 통해 모든 값을 비교하지 않아도 된다.
arrayA와 arrayB의 각 최대 공약수를 구하고, 그 최대 공약수들이 문제 조건에 만족하면, 둘중에 큰 값을 return 하면 정답이 된다.

최대 공약수를 구하는 과정에서는 유클리드 호제법을 사용했다.

유클리드 호제법

유클리드 호제법은 두 자연수 사이의 최대 공약수를 구하는 알고리즘이다.
큰 수를 작은 수로 나눈 나머지를 반복적으로 구하며 나머지가 0이 될 때까지 진행하는 방식이다.
48, 18의 최대공약수를 구하는 것을 예시로 들자면,
1. 48 % 18 = 12
2. 18 % 12 = 6
3. 12 % 6 = 0
마지막 나머지가 0이 될때 최대공약수 6을 구할 수 있다.
코드로 풀어내자면

function gcd(a, b) {
  const remainder = a % b; 
  if (remainder === 0) return b;
  return gcd(b, remainder);
}

✅ 풀이 코드

const gcd = (n1, n2) => {
    let remainder = n1 % n2;
    return n2 === 0 ? n1 : gcd(n2, remainder);
};

const canDivide = (gcdValue, arr) => {
    return arr.every(num => num % gcdValue !== 0);
};

function solution(arrayA, arrayB) {
    let answer = 0;

    let gcdA = arrayA[0];
    for (let i = 1; i < arrayA.length; i++) {
        gcdA = gcd(gcdA, arrayA[i]);
    }

    let gcdB = arrayB[0];
    for (let i = 1; i < arrayB.length; i++) {
        gcdB = gcd(gcdB, arrayB[i]);
    }

    if (canDivide(gcdA, arrayB)) {
        answer = Math.max(answer, gcdA);
    }

    if (canDivide(gcdB, arrayA)) {
        answer = Math.max(answer, gcdB);
    }

    return answer;
}