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

🏷️문제

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

🔎풀이

#유클리드 알고리즘 #최대공약수(GCD)

//최대 공약수
const gcd = (a,b) => {
    while(b !== 0){
        [a, b] = [b, a % b]
    }
    return a
}

function solution(numer1, denom1, numer2, denom2) {    
    //분수 덧셈
    const denom  = denom1 * denom2
    const numer = numer1 * denom2 + numer2 * denom1
    
    //분자 분모의 최대 공약수
    const divisor = gcd(numer, denom)
    
    //기약 분수
    const minNumer = numer / divisor
    const minDenom = denom / divisor
    
    return [minNumer, minDenom];
}

• 시간 복잡도: O(log min(numer, denom))

📌키워드

유클리드 알고리즘

const gcd = (a, b) => {
	while(b !== 0){
    	[a, b] = [b, a % b] 
    }
    return a
}

• gcd 시간 복잡도: O(log min(a,b))

 

참고)