[프로그래머스] lv0. 분수의 덧셈 (JS)

❓ 문제

코딩테스트 연습 - 분수의 덧셈 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

 

 

💡 해결하기

1️⃣ 약분하기 전 분자와 분모의 숫자 구하기

분자는 numer1 x denum2 + numer2 x denum1 의 방식으로 구할 수 있다.

분모는 denum1 x denum2 의 방식으로 구할 수 있다.

 

2️⃣ 유클리드 호제법과 재귀를 이용하여 약분하기 위한 최대공약수를 구하기

유클리드 호제법을 이용하면 숫자를 하나씩 탐색하여 최대공약수를 구하는 것보다 훨씬 효율적으로 최대공약수를 구할 수 있고, 이를 재귀 방식을 이용하면 한눈에 들어오게 코드 작성이 가능하다.

 

* 유클리드 호제법

유클리드 호제법 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

* 유클리드 호제법에서 두 숫자의 순서는 중요하지 않다. (즉, 크기에 따라 나눠지는 수와 나누는 수가 정해진다는 것이 아니다.)

 

마지막으로 약분이 되지 않은 분자와 분모의 숫자를 구한 최대공약수로 각각 나누어 그 결과를 배열에 담아 반환하면 된다.

 

 

 

💻 JS로 코드 작성하기

 

// 최대공약수 구하기
function GCD(a, b) {
  if (a % b === 0) {
    return b;
  } else {
    return GCD(b, a % b);
  }
}

function solution(numer1, denom1, numer2, denom2) {
  var result = [numer1 * denom2 + numer2 * denom1, denom1 * denom2];
  var gcd = GCD(result[0], result[1]);
  result[0] /= gcd;
  result[1] /= gcd;
  return result;
}

 

GCD 재귀 함수를 작성할 때 주의할 점은 GCD(b, a % b)를 적어줄 때 return을 적어주는 것이다.

GCD에 새로운 인자(숫자)가 들어감과 동시에 아까 실행되고 있던 GCD 함수가 종료되어야 하기 때문이다.