[프로그래머스] 분수의 덧셈(최대공약수, 최소공배수 구하기)

문제 설명

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

제한사항 : 0 <denum1, num1, denum2, num2 < 1,000

무작정 풀던 중, 뭔가 비효율적으로 풀고 있는 것처럼 느껴져 최대공약수 및 최소공배수 구하는 알고리즘을 찾아보았다.

최대공약수(GCD)

GCD란 Greatest Common Divisor로 가장 큰 공통된 약수라는 의미다. 유클리드 호제법을 사용해 구했고, 유클리드 호제법은 다음을 뜻한다

GCD(a, b) = GCD(b, r)

여기서 a, b는 비교할 숫자이고, r은 a에 b를 나눈 나머지를 뜻한다

1275, 460이라는 숫자의 최대공약수를 구하려고 할 때,
GCD(1275, 460)의 나머지(r)는 355이다. GCD(1275, 460) = GCD(460, 355)이 된다.
GCD(460, 355)의 나머지(r)는 105이다. GCD(460, 355) = GCD(355, 105)가 된다.
GCD(355, 105)의 나머지(r)는 40이다. GCD(355, 105) = GCD(105, 40)이다.
GCD(105, 40)의 나머지(r)는 25이다. GCD(105, 40) = GCD(40, 25)이다.
GCD(40, 25)의 나머지(r)는 15이다. GCD(40, 25) = GCD(25, 15)이다.
GCD(25, 15)의 나머지(r)는 10이다. GCD(25, 15) = GCD(15, 10)이다.
GCD(15, 10)의 나머지(r)는 5이다. GCD(15, 10) = GCD(10, 5)이다.
GCD(10, 5)의 나머지(r)는 5이다. GCD(10, 5) = GCD(5, 0)이다.

GCD(1275, 460)
= GCD(460, 355) = GCD(355, 105)
= GCD(105, 40) = GCD(40, 25)
= GCD(25, 15) = GCD(15, 10)
= GCD(10, 5) = GCD(5, 0)

나머지가 없다는 것 = 공통된 약수로 나누어 떨어진다는 것

1275, 460의 최대공약수는 5이다.

최소공배수

입력받은 두 수(a, b)의 곱에서 최대공약수(d)를 나눠주면 된다.

a * b / d

1275 * 460 / 5 = 117,300

• 계산한 값이 제대로 된 값인지 확인을 원한다면 여기서 쉽게 확인할 수 있다.
  https://hi098123.tistory.com/155

내가 푼 코드

class Solution {
    public int[] solution(int denum1, int num1, int denum2, int num2) {
        
        // 입력받은 두 분모의 최대공약수를 구한다.
		int gcd = gcd(num1, num2);
        
        // 입력받은 두 분모의 최소공배수를 구한다.
		int lcm = lcm(num1, num2, gcd);
        
        // 분모에 어떤 수를 곱해야 최소공배수가 나오는지 확인한 후 분자를 분모에 맞춰준다.
		int mul1 = lcm / num1;
		denum1 *= mul1;
		int mul2 = lcm / num2;
		denum2 *= mul2;
        
        // 두 분자를 더한다.
		int denum = denum1 + denum2;
		
        // 기약분수를 구해야 하므로, 합한 분자와 분모의 최대공약수를 구한다.
		int gcd2 = gcd(denum, lcm);
        
        // 최대공약수로 나눠준다.
		int[] answer = {denum / gcd2, lcm / gcd2};
		
        return answer;
        
    }
    
    // 최대공약수
    public int gcd(int num1, int num2) {
		
		boolean stop = false;
		int temp1 = num1;
		int temp2 = num2;
		
		while (!stop) {
			if (temp2 == 0) {
				break;
			}
			
			if (temp2 != 0 || temp1 % temp2 != 0) {
				int temp = temp1;
				temp1 = temp2;
				temp2 = temp % temp2;
			} else {
				stop = true;
			}
		}
		
		return temp1; 
	}
    
    // 최소공배수
    public int lcm(int num1, int num2, int gcd) {
		return (num1 * num2) / gcd;
	}
}

참고: 유클리드 호제법(최대공약수, 최소공배수)