[문제풀이 후기] 프로그래머스 #120808 - 분수의 덧셈

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

 

기본 상위 코드

const [numer1, denom1] = [1, 2];	// 분수 1
const [numer2, denom2] = [3, 4];	// 분수 2

 

첫 번째 시도 (결과 : 실패)

 

접근 방식

1. 각 분모로 나눴을 때 나머지가 0이 나오는 최소값 계산 (=최소공배수)
2. 각 분자에 최소공배수 / 각 분모 의 값을 곱한 뒤 합계 계산

let denom = 1; // 최종 분모

// 각 분모로 나눴을 때 나머지가 모두 0이 되는 최소 최종 분모 계산
while (denom % denom1 !== 0 || denom % denom2 !== 0) {
  denom++;
}

// 분자 합계
const sum = (denom / denom1) * numer1 + (denom / denom2) * numer2;

return [sum, denom];

 

실패 원인

: 분자/분모 가 서로소여야 함 (현재는 약분이 가능함) (반례 : [1,2], [1,2] => [2,2])

---

규칙

규칙 1 - 분수의 덧셈 공식

a/b + c/d
= (a * d + c * b) / (b * d)

규칙 2 - 유클리드 호제법
: 최대공약수를 계산하는 알고리즘

a, b가 있을 때, a % b 수행
- 나머지가 0이 될 때까지 b % (a % b) 수행​

=> 최대공약수 = 나머지가 0일 때의 b

 

두 번째 시도 (결과 : 성공)

 

접근 방식

1. 최대공약수 계산 함수 분리
2. 분수 계산 함수, 최대공약수 계산 함수 적용

// 최대공약수 (GCD: Greatest Common Divisor) 계산 (유클리드 호제법)
const getGcd = (dividend, divisor) => {
  if (divisor === 0) return dividend;
  return getGcd(divisor, dividend % divisor);
};

const numer = numer1 * denom2 + denom1 * numer2; // 분자
const denom = denom1 * denom2; // 분모

const gcdValue = getGcd(numer, denom); // 최대공약수

return [numer / gcdValue, denom / gcdValue]; // 약분

 

후기

어쩌다보니 최소공배수를 계산해버렸는데, 최소공배수도 최대공약수를 활용하면 효율적으로 해결이 가능할 것으로 보인다.