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

문제 설명

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

---

제한사항

• 0 <denum1, num1, denum2, num2 < 1,000

---

입출력 예denum1num1denum2num2result

1	2	3	4	[5, 4]
9	2	1	3	[29, 6]

---

입출력 예 설명

입출력 예 #1

• 1 / 2 + 3 / 4 = 5 / 4입니다. 따라서 [5, 4]를 return 합니다.

입출력 예 #2

• 9 / 2 + 1 / 3 = 29 / 6입니다. 따라서 [29, 6]을 return 합니다.

 

---

class Solution {
    public int[] solution(int denum1, int num1, int denum2, int num2) {
    	
        // 분자 denums, 분모 nums
        int denums = denum1 * num2 + denum2 * num1;
        int nums = num1 * num2;

        // 기약분수로 만들기 위해 더한 분자와 분모의 최대공약수 구하기
        int gcd = gcd(denums, nums);
 
        // 분자와 분수 약분
        return new int[]{denums / gcd , nums / gcd};
    }

    // 유클리드 호제법 최대공약수(재귀)
    public int gcd(int a, int b) {
        if (a % b == 0) {
            return b;
        }
        return gcd(b, a%b);
    }
    // 유클리드 호제법 최대공약수
    static int gcd(int a, int b){
        while(b!=0){
            int r = a%b;
            a = b;
            b = r;
        }
        return a;
    }
}

 

1. 쉬운 문제였는데 오래걸림 화남. 코드실행해서 테스트는 성공했는데 다른 테스트 케이스에서 막혔다. 
2. 알고보니 분수를 더한 후에 그 분자와 분모의 최대공약수를 구해야 했었는데.. 더하기 전에 미리 최대공약수를 구해버려서..
3. 그래도 최대공약수 알고리즘과 최소공배수 알고리즘은 좀 알게되었다... 

최소공배수 a * b / gcd 

참고

최소공배수와 최대공약수