프로그래머스 / JavaScript / 분수의 덧

• 분수의 덧셈

 

문제 설명

 

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

---

제한사항

• 0 <numer1, denom1, numer2, denom2 < 1,000

---

입출력 예

numer1	denom1	numer2	denom2	result
1	2	3	4	[5, 4]
9	2	1	3	[29, 6]

 

---

입출력 예 설명

입출력 예 #1

• 1 / 2 + 3 / 4 = 5 / 4입니다. 따라서 [5, 4]를 return 합니다.

입출력 예 #2

• 9 / 2 + 1 / 3 = 29 / 6입니다. 따라서 [29, 6]을 return 합니다.

function solution(numer1, denom1, numer2, denom2) {
   const resultNumer = numer1 * denom2 + numer2 * denom1;
   const resultDenom = denom1 * denom2;

   const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));

   const commonFactor = gcd(resultNumer, resultDenom);

   const simplifiedNumer = resultNumer / commonFactor;
   const simplifiedDenom = resultDenom / commonFactor;

   return [simplifiedNumer, simplifiedDenom];
}

// 예시 사용
console.log(solution(1, 2, 3, 4)); // [5, 4]
console.log(solution(9, 2, 1, 3)); // [29, 6]

 

1. 덧셈 공식을 사용하여 두 분수를 합친다. 

- 분자는 "내 숫자에 상대 분모를 곱한 것"과 "상대 숫자에 내 분모를 곱한 것"을 더하고, 분모는 두 분수의 분모를 곱함.

 

2. 기약분수 = 둘의 공약수가 1밖에 없는 서로소라서 더 이상 나눌 수 없는 분수. 그렇기에 분수끼리 덧셈을 하고 나서, 최대공약수로 나누면 더 이상 나눌 수 없는 기약분수가 됨.

 

3. 최대공약수 구하는 함수

- 유클리드 호제법을 이용

- A를 B로 나눈 나머지가 C일 때 (A와 B의 최대공약수) = (B와 C의 최대공약수)

- 예) 48과 21의 공약수를 구해보자.

- 48을 21로 나눈 나머지는? 6

- 21을 6으로 나눈 나머지는? 3

- 6을 3으로 나눈 나머지는 0

그렇다면 6과 3의 최대공약수는? 3이 최대공약수가 된다.

const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));

위의 함수를 살펴보면 재귀적인 방법을 사용하여 두 수의 최대공약수를 찾음. 여기서 'a'와 'b'는 두 수를 나타낸다.

함수의 기본 원리는 다음과 같다.

• 만약 'b'가 0이라면, 즉 두 수 중 하나가 0이라면, 'a'자체가 최대공약수가 된다. 그래서 'a'를 반환한다.
• 만약 'b'가 0이 아니라면, 즉 두 수가 모두 0이 아니라면, 다시 함수를 호출한다.
• 호출할 때는 'b'와 'a % b'를 인자로 사용한다. 'a % b'는 'a'를 'b'로 나눈 나머지를 나타낸다.
• 이렇게 재귀 호출을 반복하면서 'b'가 0이 되는 순간, 그 때의 'a'가 최대공약수가 된다.

간단히 말해, 두 수의 최대공약수를 구하는 방법은 하나의 수를 다른 수로 나눈 나머지를 구하고, 그 나머지를 다시 나누어지는 수로 대체하는 과정을 반복하여 나머지가 0이 되는 순간의 나누는 수가 최대공약수가 된다.

이를 재귀 함수로 구현한 것이 위의 코드이다.

 

출처: 프로그래머스 코딩 테스트 연습 : https://school.programmers.co.kr/learn/challenges

코딩테스트 연습 | 프로그래머스 스쿨

출처: 페르마가 들려주는 약수와 배수 2 이야기 : https://blog.naver.com/jamogenius/221259721978

유클리드 호제법을 이용해 두 수의 최대공약수 구하기