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

문제 요구사항 정의

• 두 분수를 더한 값을 기약 분수로 나타내야 한다.
• 분자와 분모를 순서대로 담은 배열을 리턴한다.

링크

개념 정리

기약분수

기약분수는 이미 약분된 분수를 뜻한다. 따라서 분모와 분자가 1 이외에는 공약수가 없다.

문제 풀이

✓ 최소공배수를 이용하여 풀기

최소공배수는 두 수에 서로 공통으로 존재하는 배수 중 가장 작은 수를 뜻한다.

function solution(numer1, denom1, numer2, denom2) {
    let top = numer1 * denom2 + numer2 * denom1;
    let bottom = denom1 * denom2;
    let lcm = 1;
    
    for (let i = 1; i <= top; i++) { // 최소공배수 구하기
        if (top % i === 0 && bottom % i === 0) {
            lcm = i;
        }
    }
    return [top/lcm, bottom/lcm];
}

✓ 최대공약수를 이용하여 풀기

최대공약수는 두 수에 서로 공통으로 존재하는 약수 중 가장 큰 수를 뜻한다. 이를 구하기 위한 유클리드 호재법 알고리즘이 존재한다.

• 유클리드 호재법은 MOD 연산을 반복하면 된다! (참고)

1112와 695의 최대공약수 구하기

1112 mod 695 = 417
695 mod 417 = 278
417 mod 278 = 139
278 mod 139 = 0

나머지가 0이 되었을 때 마지막 계산에서 나누는 수로 사용된 139가 1112와 695의 최대공약수이다. 

function solution(numer1, denom1, numer2, denom2) {
    let top = numer1 * denom2 + numer2 * denom1;
    let bottom = denom1 * denom2;
    
    const gcf = (top, bottom) => {
        while (true) {
            let reminder = top % bottom;
          	// 나머지가 0이 되었을 때의 분모를 리턴한다(=> 최대공약수).
            if (reminder === 0) return bottom; 
          	// 아니라면 MOD 연산을 반복한다. 
            top = bottom;
            bottom = reminder;
        }
    }
    
    return [top/gcf(top, bottom), bottom/gcf(top, bottom)];
}