lv0 - 분수의 덧셈 (자바)

문제 설명

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

입출력 예

numer1	denomm1	numer2	denom2	result
1	2	3	4	[5, 4]
9	2	1	3	[29, 6]

생각정리

1. 분수의 덧셈은 분모 (a, b)를 같은 값으로 맞춰야 한다.

2. 분모의 최소공배수를 찾아야한다.

• 처음에는 for문을 써보려고 했지만 배수가 되는 인수가 다를 수 밖에 없어서 안된다.
• a와 b의 배수를 각각 배열에 담아서 비교해보려 했지만, 큰 수일 경우에 너무 큰 배열이 필요하다.
• 두 수를 곱하면 되지 않나? ==> no 서로소일 경우만 성립한다. 공약수가 있는경우 곱하면 '최소' 공배수가 아니다.

3. 최소 공배수 = a*b / 최대공약수 // 중학생때 배웠던 공식이 떠올랐다.

4. 최대공약수를 구하면 최소공배수를 구할 수 있다. 근데 코드로 어떻게 구현하지?

결국 최소공배수 구하는 방법을 검색했다. 최대공약수를 구할때 '유클리드 호제법'을 사용한다.

유클리드 호제법

- a 와 b 의 최대공약수를 구하는 방법 - a 가 b 보다 클때 (a, b는 자연수) a를 b로 나누었을때 나머지가 0 이면 b는 a 와 b 의 최대공약수다. 나머지가  r 이라면, b를 r로 나눈 값이 0 이될때 r이 최대공약수가 된다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복한다. 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

이를 이용하여 최대 공약수 구하는 코드를 짰다

public int getGCD(int a, int b) {
    if (a%b == 0) { 
        return b;
    } else {
        return getGCD(b, a % b);
    }
}

재귀함수를 이용한다. 최대공약수를 구했으므로 최소공배수도 구할 수 있다.

public int getLCM(int a, int b) {
    if (a % b == 0) {
        return a * b;
    } else {
        int gcd = getGCD(a, b);
        return a * b / gcd;
    }
}

최종적인 답안은 다음과 같다

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int[] answer = new int[2]; 
        
        int b = getLCM(denom1, denom2);
        int a = ((b/denom1)*numer1) + ((b/denom2)*numer2);
        //최소공배수로 맞춰진 분모에 따라 분자 계산
        
        int gcd = getGCD(a, b); 
        answer[0] = a / gcd; //기약분수 만들기
        answer[1] = b / gcd; //기약분수 만들기
        
        return answer;
    }
    
    public int getGCD(int a, int b) {
        if (a % b == 0) {
            return b;
        } else {
            return getGCD(b, a % b);
        }
    }
    
    public int getLCM(int a, int b) {
        if (a % b == 0) {
            return a * b;
        } else {
            int gcd = getGCD(a, b);
            return a * b / gcd;
        }
    }
}