[JavaScript] 분수의 덧셈

프로그래머스 문제 풀다가 마주친 벽
최대공약수를 구해야 한다는건 알겠는데 이를 코드로 풀어내질 못해서 결국 찾아보고 기억해두기 위해 적어둔다.

---

1. 각 분수를 더한 값 구하기

function solution(numer1, denom1, numer2, denom2) {
	const numer3 = numer1 * denom2 + denom1 * denom2
    const denom3 = denom1 * denom2
}

2. 분자와 분모의 최대공약수 구하기

최대공약수를 구하는 방법엔 유클리드 호제법이란 알고리즘 있다.
호제법이란 두 수가 서로(互, 서로 호) 상대방의 수로 나누어(除, 덜 제) 원하는 수를 얻는 알고리즘이라고 한다.

원리는 아래와 같다.

1. 둘 중 큰 수를 작은 수로 나눈다.
2. 이때 나머지가 0이 된다면 작은 수가 최대공약수.
3. 나머지가 0이 아니라면 작은 수를 나머지로 나눈다.
4. 이를 반복하다가 나머지가 0이 되면 그 수가 두 수의 최대공약수가 된다.

사실 원리만 보면 이해가 안되는데 예시를 보니 이해가 됐다.

78696과 19332의 최대공약수 구하기

78696 ＝ 19332×4 ＋ 1368
(큰 수를 작은 수로 나눈 나머지가 0이 아니기 때문에 작은 수를 다시 나머지로 나눔)
19332 ＝ 1368×14 ＋ 180
1368 ＝ 180×7 ＋ 108
180 ＝ 108×1 ＋ 72
108 ＝ 72×1 ＋ 36
72 ＝ 36×2 ＋ 0

따라서 최대공약수는 36

이걸 코드로 옮겨보면 아래와 같다.

function calGcd(a, b) {
	// b가 a보다 크다면 나머지가 a가 되므로 셋 째 줄에서 자리가 바뀌어 계산됨
	const remainder = a % b
    if(remainder === 0) return b // 나머지가 0이라면 작은 수 b가 최대공약수
  	return calGcd(b, remainder) // 아니라면 작은 수 b와 나머지를 재계산
}

참고로 remainder는 나머지, gcd는 greatest common divisor의 약자로 최대공약수를 의미한다.

이를 이용해서 함수를 완성하면

function solution(numer1, denom1, numer2, denom2) {
    const numer3 = numer1 * denom2 + numer2 * denom1
    const denom3 = denom1 * denom2
    const calGcd = (a, b) => {
        const remainder = a % b
        return remainder === 0 ? b : calGcd(b, remainder)
    }
    const gcd = calGcd(numer3, denom3)
    return [numer3/gcd, denom3/gcd];
}