[프로그래머스/JS] 분수의 덧셈

🧐 Problems

첫 번째 분수의 분자와 분모를 뜻하는 ``numer1``, ``denom1``, 두 번째 분수의 분자와 분모를 뜻하는 ``numer2``, ``denom2``가 매개변수로 주어집니다. 두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.

 

💡 Solutions

const gcd = (num1, num2) => num2 === 0 ? num1 : gcd(num2, num1 % num2);

const solution = (numer1, denom1, numer2, denom2) => {
    const numer = numer1 * denom2 + numer2 * denom1;
    const denom = denom1 * denom2;
    const frac_gcd = gcd(numer, denom);
    
    return [numer / frac_gcd, denom / frac_gcd];
};

코드 설명

우선 통분을 통해 두 분수의 분모 값을 같게 만들어준 뒤, 분수의 합을 구해줍니다. 그렇게 두 분수를 더한 값의 분자는 ``numer`` 변수에, 분모는 ``denom`` 변수에 저장됩니다.

 

이 때, 문제에서 두 분수의 합을 기약 분수(분모와 분자가 공통 약수를 가지지 않는 분수)로 나타내라 하였으므로, 최종 분수를 구하기 위해선 분모와 분수의 최대공약수로 나눠줘야 합니다.

 

최대공약수를 구하는 간단한 방법은 유클리드 호제법이 있습니다.

유클리드 호제법이란, 두 수의 최대공약수를 구하는 간단하고 효과적인 알고리즘입니다. 고대 그리스 수학자 유클리드가 제시한 방법이라 그의 이름을 따 유클리드 호제법이라 칭합니다.

 

구하는 방법은 다음과 같습니다.

숫자 ``a``와 ``b``가 있고 ``a``가 ``b``보다 클 때, 두 수를 나눈 나머지를 구합니다. 이때, 나머지가 0이라면 둘 중 더 작은 ``b``가 두 수의 최대공약수가 됩니다. 만약 0이 아니라면, ``b``와 앞서 구한 나머지를 가지고 나머지 값을 다시 구해줍니다. 이렇게 나온 나머지 값이 0이 나올 때까지 반복해 구해주면 됩니다.

 

유클리드 호제법을 코드로 작성하면 다음과 같습니다.

const gcd = (a, b) => b === 0 ? a : gcd(b, a % b)

 

코드에서는 `a`와 `b`를 작성할 때 크기를 고려하지 않아도 됩니다. ``a``의 크기가 커야 정상적으로 계산되긴 하지만 재귀함수로 작성해주었으므로 ``a``의 크기가 더 작으면 자동적으로 ``a``와 ``b``의 위치가 바뀌기 때문입니다.

 

유클리드 호제법을 사용하지 않고 최대공약수를 구할 수도 있습니다.

const gcd = (num1, num2_ => {
    let result = 1;
    for (let i = Math.min(num1, num2); i >= 1; i--) {
        if (num1 % i === 0 && num2 % i === 0) {
            result = i;
            break;
        };
    };
    return result;
};

둘 중 더 작은 수가 1이 될 때까지 반복하며 두 개 값을 나눠줍니다. 이 때, 두 값의 나머지가 모두 0이 되는 ``i``값이 두 수의 최대공약수가 됩니다.