[프로그래머스/JAVA] 최대공약수와 최소공배수

문제 설명
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

제한 사항
두 수는 1이상 1000000이하의 자연수입니다.
입출력 예

n	m	return
3	12	[3, 12]
2	5	[1, 10]

 

입출력 예 설명

입출력 예 #1
위의 설명과 같습니다.

 

입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

 

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        int gcd = 0; // 최대공약수
        int lcm = 0; // 최소공배수
        int num = 1;
        
        while(num<=n*m) {
        	if(m%num==0 && n%num==0 ) { // 입력받은 두 수가 num으로 나누어떨어지면
        		gcd = num; // num을 최대공약수로
        	}
        	if(lcm == 0 && m*num%n==0) lcm = m*num; // 
        	num++;
        }
        answer[0] = gcd;
        answer[1] = lcm;
        return answer;
    }
}

 

통과는 됐다.

 

 > 최대공약수(GCD) 계산
현재 코드에서는 num이 n과 m 모두 나누어떨어질 때마다 gcd를 갱신하고 있는데, 이렇게 하면 마지막에 나누어떨어지는 값이 최대공약수가 된다. 

 

 > 최소공배수(LCM) 계산
현재 코드에서는 lcm이 0일 때만 m * num을 lcm에 대입하고 있습니다. 이것은 첫 번째 나누어떨어지는 값이 최소공배수가 됩니다.

---

위 방법은 비효율적인 방법이라고..

다른 방법을 찾다가 유클리드 호제법이라는 것을 찾았다.

 

자세한 설명은 아래와 같다.

유클리드 호제법(Euclidean Algorithm)은 두 수의 최대공약수(GCD)를 구하는 방법 중 하나로, 고대 그리스 수학자 유클리드(Euclid)에 의해 제시된 방법입니다. 이 알고리즘은 두 수 a와 b에 대해 GCD(a, b)를 계산하는데 사용됩니다.

알고리즘의 핵심 아이디어는 다음과 같습니다:

1. 두 수 a와 b의 최대공약수를 GCD(a, b)라고 했을 때, GCD(a, b)는 GCD(b, a % b)와 같습니다. 여기서 "%"는 나머지를 나타냅니다.
2. 위의 성질을 계속해서 반복하면, 언젠가는 나머지가 0이 되는 순간이 옵니다. 이때의 나머지가 0인 수가 두 수의 최대공약수가 됩니다.

간단한 예시를 통해 유클리드 호제법을 이해해봅시다. 두 수 48과 18의 최대공약수를 구하는 과정은 다음과 같습니다:

1. GCD(48, 18) → GCD(18, 48 % 18) → GCD(18, 12) → GCD(12, 18 % 12) → GCD(12, 6) → GCD(6, 12 % 6) → GCD(6, 0)

나머지가 0이 되었을 때, 나머지가 0이 아닌 직전의 수가 두 수의 최대공약수입니다. 따라서 GCD(48, 18) = 6이 됩니다.

이 알고리즘은 재귀적으로 구현될 수 있지만, 반복문을 사용하여도 효과적으로 구현할 수 있습니다. 코드 예시에서 사용한 getGCD 함수가 이 방법을 사용한 것입니다.

구현

public int[] solution(int n, int m) {
    int[] answer = new int[2];

    // 최대공약수 계산 (유클리드 호제법)
    int gcd = getGCD(n, m);

    // 최소공배수 계산 (두 수의 곱 / 최대공약수)
    int lcm = (n * m) / gcd;

    answer[0] = gcd;
    answer[1] = lcm;
    return answer;
}

// 유클리드 호제법으로 최대공약수 계산
private int getGCD(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}