Programmers 120808 분수의 덧셈 Javascript

https://school.programmers.co.kr/learn/courses/30/lessons/120808

프로그래머스

---

numer1 / denom1 + numer2 / denom2의 결과를 기약분수로 나타내는 문제이다.

 

분수 덧셈의 과정을 생각해보면

 

1. 두 분모의 최소공배수를 구한다.

2. 최소공배수를 각 분모로 나눈 만큼 분자에 곱해준다. 

3. 통분된 두 분수를 더해준다.

 

단계를 가진다.

---

우선 두 수의 최소공배수는 두 수의 곱에 최대공약수를 나눔으로써 구할 수 있다.

 

최대공약수는 유클리드 호제법을 재귀함수를 이용해 구할 수 있다.

유클리드 호제법

12와 18의 최대공약수 6을 구하는 과정

a. 12를 18로 나눈 나머지 12를 구한다.
b. 18을 12로 나눈 나머지 6을 구한다.
c. 12를 6으로 나눈 나머지 6을 구한다.
d. 6을 6으로 나눈 나머지 0을 구한다.
e. 결과가 0이 되었으므로 최대공약수는 6이다.

---

위 로직을 그대로 구현해 보면 다음과 같다.

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

function solution(numer1, denom1, numer2, denom2) {
  let lcm = (denom1 * denom2) / GCD(denom1, denom2);
  let top1 = (numer1 * lcm) / denom1;
  let top2 = (numer2 * lcm) / denom2;

  console.log(top1, top2, lcm);

  var answer = [top1 + top2, lcm];
  return answer;
}

 

solution(1,2,3,4)를 실행하면

 

1. lcm = 8 / 2 = 4

2. top1 = 1 * 4 / 2 = 2

3. top2 = 3 * 4 / 4 = 3

따라서 2/4 + 3/4 = 5/4의 정답이 나온다.

 

하지만 이 코드는 문제점이 있다. 무엇일까?

---

바로 덧셈 결과에서의 약분을 생략한 것이다.

 

이것은 결과의 분자, 분모의 최대공약수를 구해서 각각 나누어주는 것으로 해결할 수 있다.

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

function solution(numer1, denom1, numer2, denom2) {
  let lcm = (denom1 * denom2) / GCD(denom1, denom2);
  let top1 = (numer1 * lcm) / denom1;
  let top2 = (numer2 * lcm) / denom2;

  let numer = top1 + top2;
  let gcd = GCD(numer, lcm);

  var answer = [numer / gcd, lcm / gcd];
  console.log(answer);
  return answer;
}

solution(4, 4, 1, 2); // 3/2