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

프로그래머스 코딩테스트 입문을 다 풀면 받는 머쓱이 스탬프를 얻기 위해서
어제부터 day1, day2를 풀어나가고 있다.
그런데 분수의 덧셈에서 최대공약수를 구하는 방법이 너무 생각이 안나서 구글링했더니
대다수의 사람이 유클리드 호제법을 이용해서 문제를 해결하고 있었다.
그래서 이번 글에서는 유클리드 호제법과 코드를 살펴보고자 한다.

유클리드 호제법

• 왜 사용하는가?
  • 우선 최대공약수를 구해야하는 수가 크면 계산이 매우 복잡해지고,
  • 약수를 찾기 어려운 경우가 많다 (예를 들면, 403과 155)
  • 그래서 유클리드 호제법을 이용해 보다 쉽게 계산할 수 있다.
• 로직
  • a와 b가 있을 때 (a>b), (a÷b)값이 0이면 => 최대공약수는 b
  • 0이 아니라면 => b와 (a÷b)의 나머지 값을 다시 나눈다.
  • 서로 나누어 진다면 (a÷b)가 최대공약수 => 아니라면 위에 방법을 반복

분수의 덧셈

// 최대 공약수 함수
function gcd(numer, denom){

    if(numer % denom === 0) {
        return denom
    } else {
        var rest = numer % denom;
        return gcd(denom, rest)
    }
    
    // 다른 사람들은 한 줄로 깔끔하게 코드를 작성했더라..
    // return numer % denom === 0 ? denom : gcd(denom, numer % denom)
};

function solution(numer1, denom1, numer2, denom2) {
    var answer = [];
    var numer = (numer1 * denom2) + (numer2 * denom1)
    var denom = denom1 * denom2
    
    var ans = gcd(numer, denom)
    
    answer[0] = numer / ans
    answer[1] = denom / ans
    
    return answer;
}