[프로그래머스 코딩테스트] N개의 최소공배수

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

풀이

유클리드 호제법을 사용해 문제를 해결한다.
(A*B)/A와 B의 최대 공약수의 공식을 이용해 최소 공배수를 구할 수 있다.

예를 들어 60과 48이 있다고 할 때 수학적 공식으로 풀면 이와 같다.

유클리드 호제법을 사용하면,

이와 같은 방법으로 최대 공약수와 최소 공배수를 손쉽게 구할 수 있다.

내 코드

class Solution {
    public int solution(int[] arr) {
        return getLCM(arr);
    }
    
    public int getLCM(int[] arr){ //최소 공배수
        if(arr.length == 1) return arr[0];
        
        int gcd = getGCD(arr[0], arr[1]);
        int lcm = (arr[0] * arr[1]) / gcd;
        
        for(int i=2; i<arr.length; i++){
            gcd = getGCD(lcm, arr[i]);
            lcm = (lcm * arr[i]) / gcd;
        }
        
        return lcm;
    }
    
    public int getGCD(int a, int b){ //최대 공약수
        if(a % b == 0) return b;
        return getGCD(b, a%b);
    }
}

이를 코드에 적용시키려면, 먼저 getLCM() 메서드와 getGCD() 메서드를 만들어준다. 배열의 0번째와 1번째 숫자를 이용해 먼저 최대 공약수를 찾아 변수 gcd에 저장해주고, gcd를 이용해 최소 공배수를 구해준다.
이렇게 구해진 최소 공배수와 배열의 2번방부터 끝까지 반복문을 돌려 최종적으로 답이 되는 최소 공배수를 구해준다.