[프로그래머스/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]을 리턴해야 합니다.

---

문제를 풀 수 있는 방법은 유클리드 호제법을 사용하느냐 or 하지 않느냐로 나뉘는 것 같다.

우선 유클리드 호제법을 사용하지 않은 소스코드는 아래와 같다.

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        int min = n > m ? m : n;
        
        for(int i = 1; i <= min; i++){
            if(n % i == 0 && m % i == 0){
                answer[0] = i;
            }
        }
        answer[1] = (n * m) / answer[0];
        return answer;
    }
}

나름 간결하다. 반대로 유클리드 호제법을 사용한 소스코드는 아래와 같다.

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        if(n > m){
            int temp = n;
            n = m;
            m = temp;
        }
        answer[0] = gcd(n, m);
        answer[1] = (n * m) / answer[0];
        
        return answer;
    }
    
    public int gcd(int a, int b){
        if(a % b == 0){
            return b;
        }
        return gcd(b, a%b);
    }
}

최대공약수를 구하는 함수(gcd)를 새로 만들어서 코드 자체는 길어졌지만 속도를 비교해보니 유클리드 호제법을 이용한 소스코드가 더 빨랐다!!

유클리드 호제법 X	유클리드 호제법 O

사실 내 머릿속에서 유클리드가 더 효과적이라곤 생각 못했는데 속도면에서는 몇 배 이상 차이가 나는 것 같다.

이제 최대공약수와 최소공배수 문제에 머리 아프기 싫어서 그냥 유클리드 호제법을 이용한 소스코드를 외워버렸다.

 

최소공배수를 구하는 핵심 공식은 아래와 같다.

두 수 a, b가 존재할 때 최소공배수는 a * b / 최대공약수

해당 공식이 성립하는 이유는 "정수론(1) - 최대공약수, 최소공배수, 유클리드 호제법"에서 잘 다뤄주셨다!

 

---

유클리드 호제법

A를 B로 나눈 몫을 Q라 하고, 나머지를 R이라고 했을 때, gcd(A, B) = gcd(B, R) 이다.

유클리드 호제법은 위와 같은 정리로 이루어진 알고리즘이다.

A % B를 R이라고 했을 때, gcd(A, B) = gcd(B, A%B) 인 것이다. 소스코드를 확인하면 그대로 재귀함수에 적혀진 것을 확인할 수 있다.

 

(2023.10.05 수정)