[프로그래머스] 분수의 덧셈 - JavaScript

문제

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

풀이

function solution(numer1, denom1, numer2, denom2) {
    // 분자
    let numer = (numer1 * denom2) + (numer2 * denom1)
    // 분모
    let denom = denom1 * denom2
    
    // 1부터 분자와 분모를 약분할 수 있는 수가 있는지 확인해봄 
    for ( let i = 1; i <= denom; i++) {
        if ( numer % i === 0 && denom % i === 0 ) gcd = i
    }
    
    return [numer / gcd, denom / gcd];
}

다음에는 유클리드 호제법으로도 한 번 풀어보고 싶다 생각되어 추가로 정리해보았다.

참고) 유클리드 호제법: 최대공약수 구하기

유클리드 호제법은 최대공약수를 구할 수 있는 알고리즘 중 하나이다. 간단히 정리하면,

A > B 이고 A / B 의 나머지를 R이라고 했을 때,

  R === 0 이면, A, B의 최대공약수는 B
  (e.g. 4 / 2 = 2, (R = 0)일 때 최대 공약수는 2)
  
  R != 0 일 때는, 
  B / 2 를 하고 나머지를 R2라고 했을 때
  R2 === 0 이면, A, B 의 최대공약수는 R이 된다.
  (e.g. 
	5 / 2 = 2, (R = 1)
	2 / 1 = 2, (R = 0) -> 최대공약수는 R인 1)

결국 이 과정을 반복하여 R(n)이 0이 되면, 최대공약수는 R(n-1)이 된다.

(재귀 코드)

function Euclidean(a, b) {
  let result;
  const remainder = a % b;
  if (remainder === 0) {
    result = b
  } else {
    result = Euclidean(a, remainder);
  }
  return result;
}