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

문제

문제 설명

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

제한 사항

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

입출력 예

numer1	denom1	numer2	denom2	result
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 합니다.

풀이

결과로 아래와 같은 식이 나와야된다.

\[\frac{numer1}{denom1} + \frac{numer2}{denom2}=\frac{result[0]}{result[1]}\]

하지만 기약 분수로 나타내야 됐기 때문에 아래와 같은 풀이로 하기로 했다.

생각한 방식

1. 통분하여 공통분모로 값을 맞춘다.
2. 공통분모에서 최대공약수를 나눠 기약분수로 만들어준다.

풀이 방식

1. numer1과 denom2를 곱하고 denom1과 numer2를 곱하여 양 값을 더한다. 이 값 변수명을 numer에 하였다.
2. denom1과 denom2를 곱하여 기약분수를 만들어 이 값을 변수명 denom으로 하였다.
3. 재귀를 사용하여 두 정수의 최대공약수를 계산한다.

   public static int getGCD(int num1, int num2) {
    // 만약 num1이 num2로 나누어 떨어진다면, num2가 최대공약수이다.
    if (num1 % num2 == 0) {
        return num2;
    }
    // 그렇지 않으면, num2와 num1을 num2로 나눈 나머지를 인수로 하여 재귀 호출한다.
    return getGCD(num2, num1 % num2);
   }
   

아래와 같은 원리를 기초로 유클리드 호재법 사용

• 두 수 a와 b (a > b)의 최대공약수는 b와 a를 b로 나눈 나머지의 최대공약수와 같다.

제출 코드

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int numer = numer1 * denom2 + denom1 * numer2; // 분자
        int denom = denom1 * denom2; // 분모
        int gcd = getGCD(numer, denom); // denom1과 denom2의 최대공약수 값
        int[] answer = {numer / gcd, denom / gcd}; // 분자와 분모를 최대공약수로 나눈다.
        return answer;
    }

    // 최대공약수를 구하는 static 메서드
    public static int getGCD(int num1, int num2) {
        if (num1 % num2 == 0) {
            return num2;
        }
        return getGCD(num2, num1 % num2);
    }
}