[Programmers/Java/Lv.0] 9.분수의 덧셈

문제 설명

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

 

제한 사항

0 <`numer1`, `denom1`, `numer2`, `denom2` < 1,000

 

입출력 예

numer1	denom1	numer2	denom2
1	2	3	4
9	2	1	3

`입출력 예 #1` 1 / 2 + 3 / 4 = 5 / 4입니다. 따라서 [5, 4]를 return 합니다.
`입출력 예 #2` 9 / 2 + 1 / 3 = 29 / 6입니다. 따라서 [29, 6]을 return 합니다.

 

나의 풀이

분모, 분자를 `최대공약수(GCD)로 한번만 나누어주면` 분자와 분모는 더 이상 서로 나눠질 수 없는 상태, 즉 기약분수가 된다. 기약분수는 분자와 분모가 서로소(공통인 약수가 1뿐인 상태)인 분수이다.

그러면 최대공약수를 구하고 최대공약수로 분모 분자를 나누어주면 이 문제는 해결된다.

`최대 공약수`는 공약수 중에서 가장 큰 공약수를 최대 공약수라고한다.

`공약수`는 두 개 이상의 자연수의 공통된 약수이다. 즉 분모와 분자 둘 다 같은 값으로 나누어줬을때 둘 다 나머지가 0이면 된다. 이 공약수를 분모와 분자보다 작거나 같은값까지 확인하여 최대값을 찾는다.

import java.util.Arrays;

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        if (0 < numer1 && numer1 < 1000 && 0 < denom1 && denom1 < 1000 && 0 < numer2 && numer2 < 1000 && 0 < denom2 && denom2 < 1000) {
            int denominator = denom1 * denom2; // 분모 commonDen
            int molecule = denom2 * numer1 + denom1 * numer2; // 분자 commonNumer

            int gcd = 1;

            // 최대공약수 찾기
            for (int i = 1; i <= molecule && i <= denominator; i++) {
                if (molecule % i == 0 && denominator % i == 0) {
                    gcd = i;
                }
            }

            molecule = molecule / gcd; // 기약분수 분자
            denominator = denominator / gcd; // 기약분수 분모

            int[] answer = {molecule, denominator};

            return answer;
        } else {
            return new int[0]; // 빈 배열 반환
        }
    }

    public static void main(String args[]) {
        Solution st = new Solution();
        int[] test1 = st.solution(1, 2, 3, 4);
        int[] test2 = st.solution(9, 2, 1, 3);
        System.out.println(Arrays.toString(test1));
        System.out.println(Arrays.toString(test2));
    }
}