JAVA 알고리즘 - 최대공약수와 최소공배수

문제 설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요.

배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다.

예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

제한 사항

두 수는 1이상 1000000이하의 자연수입니다.

문제풀이

최소공배수와 최대공약수를 구하는 방법은 아래 N개의 최소공배수 구하기 글에서 설명했었습니다.

JAVA 알고리즘 - N개의 최소공배수 구하기

다시한번 리마인드 하자면, A*B / 최대공약수 -> 두 수의 최소공배수를 구하는 알고리즘이고,

최대공약수는 나머지가 0이 아닐때 까지 while 문을 통해 두 수를 나누어 리턴되는 값으로 두 수의 최대공약수를 구할 수 있습니다.

이 알고리즘을 이해하면 문제를 쉽게 접근할 수 있습니다!

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = {};
        answer = new int[2];
        answer[0] = gcd(n,m);
        answer[1] = lcm(n,m);
        
        return answer;
    }
    
    // 최소공배수 lcm(a*b / 최대공약수)
    static int lcm ( int n, int m ){
        return n*m / gcd(n, m); 
    }
    
    // 최대공약수 gcd(a, b)
    static int gcd(int n, int m){
        while ( m != 0){
            int t = n%m;
            n = m;
            m = t;
        }
        return n;
    }
}