[프로그래머스] 분수의 덧셈 (Java/자바), GCD 재귀

문제

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

 

풀이

유클리드 호제법

두수를 나누어서 나온 나머지를 이전 나머지에 다시 나누고, 0 이 나올 때까지 반복.

중지했을 때, 바로 직전의 나머지가 최대공약수

=> 재귀를 통해 구현

    private static int gcd(int a, int b){ 
        if(b == 0) return a; 
        return gcd(b, a % b); 
    }

1. 먼저 분모를 똑같이 만들어주고

2. 분자 계산

3. 분모와 분자를 최대공약수로 나눠줌

import java.util.*;
class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int[] answer = new int[2];
        int ansDenom = denom1*denom2;
        numer1 = numer1 * denom2;
        numer2 = numer2 * denom1;
        int ansNumer = numer1 + numer2;
        int min = gcd(ansNumer, ansDenom);
        answer[0] = ansNumer/min;
        answer[1] = ansDenom/min;
        return answer;
    }
    private static int gcd(int a, int b){ 
        if(b == 0) return a; 
        return gcd(b, a % b); 
    }

}