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

유클리드 호재법으로 최대공약수를 구한다 아래의 코드를 보면 GCD 라는 함수로 각 분모와 분자의 값을 파라미터로 전달한다.

전달 받은 파라미터를 재귀함수로 나머지가 0이 나올때까지 함수를 실행하게된다 쉽게 설명해보자면

1/2 + 3/4 = 5/4 일때

먼저 분자의 합은 10이고 분모의 합은 6이다.

이상태에서 GCD함수를 호출하고 num1에는 10, num2에는 6이들어가게된다

10 % 6 은 나머지가 4이기때문에 if문을 종료하고 return으로 다시 GCD 함수를 호출한다

이번에는 6, 4(10%6) 이며 다시 나누게되면 나머지가 2이기때문에 전과 같은 방법으로 반복을 하게된다.

이렇게 반복되다보면 최대공약수를 구할수 있게된다 

class Solution {
    public int GCD(int num1, int num2) {
        if (num1 % num2 == 0)
            return num2;
        return GCD(num2, num1 % num2);
    }

    public int[] solution(int denum1, int num1, int denum2, int num2) {
        int[] answer;

        denum1 *= num2;
        denum2 *= num1;

        answer = new int[]{denum1 + denum2, num1 * num2};

        int greatest_common_divisor = GCD(answer[0], answer[1]);
        answer[0] /= greatest_common_divisor;
        answer[1] /= greatest_common_divisor;

        return answer;
    }
}