[코딩테스트] 분수의 덧셈

분수의 덧셈 문제를 풀고 있었는데, 대충 플로우 까진 생각해냈는데

도저히 최대공약수를 찾을 방법을 알지 못했다. 

그래서 찾은 답안이 이건데 이게 가장 기초적인 최대공약수를 구하는 로직이다. 

function solution(denum1, num1, denum2, num2) {
    let topNum = denum1 * num2 + denum2 * num1
    let bottomNum = num1 * num2
	let gcd = 0
    for(let i = 0; i < topNum; i++) {
        if(topNum%i === 0 && bottomNum%i === 0) {
            gcd = i
        }
    }
    return [topNum/gcd, bottomNum/gcd]
}

for문을 안쓴지 오래돼서 오랜만에 for문을 보니 조금 어지러웠는데

(실무에서 하다보면 그냥 배열에 있는 요소들을 하나하나 꺼내서 쓰는거 제외하곤 딱히 루프 횟수 따져가며 연산할 일이 없기 때문에..)

for문을 안쓰고 쓴 식도 있다고 하여 그것을 보니 재귀함수를 통해 풀어내고 있었다.

이게 유클리드 호제법이라는 것이라고 한다.

function fnGCD(a, b){
    return (a%b)? fnGCD(b, a%b) : b;
}

function solution(denum1, num1, denum2, num2) {
    let denum = denum1*num2 + denum2*num1;
    let num = num1 * num2;
    let gcd = fnGCD(denum, num); //최대공약수

    return [denum/gcd, num/gcd];
}

 

결론은 분모의 값을 곱해서 같은 분모로 통일해주고 분자들 역시 서로의 분모를 곱해주어 덧셈을 해주면 

기약분수는 아니지만 덧셈이 끝난 상태가 되는데, 기약분수로 만들기 위한 과정에 덧셈이 끝난 분모, 분자의 최대공약수를 찾는 문제가

이 문제의 난관이었던 것 같다.

아무래도 많이 사용되어야할 개념인듯하니 유클리드 호제식 같은 내용은 조금 알아두는게 코테에선 유리할지도 모르겠다.