[프로그래머스] Java : N개의 최소공배수

문제)

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

입출력 예)

arr	result
[2, 6, 8, 14]	168
[1, 2, 3]	6

 

---

 

제가 생각한 알고리즘은 두수의 최소공배수를 구하는 방법을 확장시킨겁니다.

예를 들어 3과 4의 최소공배수는 12이고, 2와 6의 최소공배수는 6입니다.

이를 구하는 방법은 a * b / (최대공약수) 를 떠올리시면 됩니다.

저는 그래서 배열의 앞뒤 원소를 비교해 뒤 원소를 바꿔주기는 방식을 택했습니다.

 

---

 

class Solution {
    public int solution(int[] arr) {
        int answer = 0;
        int len = arr.length;
        
        if (len >= 2) {
            for (int i=0; i<len - 1; i++) {
                
                int maxNum = 1;
                
                // 최대공약수 찾기
                for (int j=1; j<=arr[i]; j++) {
                    if (arr[i] % j == 0 && arr[i+1] % j == 0 && i < len - 1) {
                        maxNum = j;
                    }
                }
                
                // arr[i+1]에 최소공배수 넣어주기
                arr[i+1] = (arr[i] * arr[i+1]) / maxNum;
            }
        }
        
        // 마지막 원소 반환
        return arr[len-1];
    }
}