
🏷️문제
첫 번째 분수의 분자와 분모를 뜻하는 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))
참고)
'알고리즘 > JavaScript' 카테고리의 다른 글
| [JS] 몫 / 나머지 구하는 법 (feat. 정수) (0) | 2024.08.27 |
|---|---|
| [프로그래머스/JS] 평행 (0) | 2024.08.27 |
| [프로그래머스/JS] 옹알이(1) (0) | 2024.08.27 |
| [코테의정석/JS] 변수와 자료형 (0) | 2024.06.26 |