[Java] 최대공약수 (유클리드 호제법)

아래의 예제는 [프로그래머스 - 분수의 덧셈] 입니다.

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

 

최대공약수

정의)

공약수(두 개 이상의 자연수의 약수 중에서 공통인 것) 중에서 가장 큰 수

class Solution {
    public int[] solution(int denum1, int num1, int denum2, int num2) {
        
        denum1 *= num2;
        denum2 *= num1;
        int[] answer = new int[]{denum1 + denum2, num1 * num2};
        int max = 1;
        
        for(int i = 1; i <= answer[0] && i <= answer[1]; i++) {
            if(answer[0] % i == 0 && answer[1] % i == 0) {
                max = i;
            }
        }
        answer[0] /= max;
        answer[1] /= max;
        
        return answer;
    }
}

 

유클리드 호제법

개념)

두 정수 a, b의 최대공약수를 G(a, b)라고 하자.
정수 a, b, q, r (b ≠ 0)에 대하여 a = bq + r이면 G(a, b) = G(b, r)가 성립한다.

 

특징)

• 소인수 분해하지 않고 최대공약수를 구할 수 있다.
• 큰 수들의 최대공약수를 구할 때 유용하게 사용할 수 있다.

class Solution {
    public int GCD(int num1, int num2) {
        if (num1 % num2 == 0) {
            return num2;
        }
        return GCD(num2, num1 % num2);
    }
    
    public int[] solution(int denum1, int num1, int denum2, int num2) {
        
        denum1 *= num2;
        denum2 *= num1;
        int[] answer = new int[]{denum1 + denum2, num1 * num2};
        int max = GCD(answer[0], answer[1]);
        
        answer[0] /= max;
        answer[1] /= max;
        
        return answer;
    }
}