[프로그래머스] N개의 최소공배수 (JAVA)

문제 설명

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

제한 사항

arr은 길이 1이상, 15이하인 배열입니다.
arr의 원소는 100 이하인 자연수입니다.

My Code

1트

import java.util.*;
class Solution {
    public int solution(int[] arr) {
        Arrays.sort(arr);
        int len = arr.length, mul=1, max=arr[len-1];
        while(arr.length>1) {
            int idx=0;
            while(idx<arr.length-1 && (arr[len-1]*mul)%arr[idx]==0) {
                idx++;
            }
            if(idx==len-1) break;
            mul++;
        }
        return arr[len-1]*mul;
    }
}

테스트 1 〉 통과 (0.41ms, 80.3MB)
테스트 2 〉 통과 (0.37ms, 75.5MB)
테스트 3 〉 통과 (0.47ms, 76.4MB)
테스트 4 〉 통과 (0.36ms, 72.4MB)
테스트 5 〉 통과 (0.35ms, 71.8MB)
테스트 6 〉 통과 (5.19ms, 74.3MB)
테스트 7 〉 통과 (1.20ms, 87.8MB)
테스트 8 〉 통과 (0.40ms, 89.4MB)
테스트 9 〉 통과 (1.43ms, 75.7MB)
테스트 10 〉 통과 (3.16ms, 73.6MB)

2트

class Solution {
    public int solution(int[] arr) {
        int ret = arr[0];
        for(int i=1 ; i<arr.length ; i++) {
            int g = helper(ret, arr[i]);
            ret = (ret*arr[i])/g;
        }
        return ret;
    }
    public int helper(int a, int b) {
        if(b>a) return helper(b,a);
        while(b!=0) {
            int mod = a%b;
            a = b;
            b = mod;
        }
        return a;
    }
}

테스트 1 〉 통과 (0.02ms, 77.1MB)
테스트 2 〉 통과 (0.02ms, 73.7MB)
테스트 3 〉 통과 (0.01ms, 68.7MB)
테스트 4 〉 통과 (0.01ms, 72.4MB)
테스트 5 〉 통과 (0.02ms, 73.3MB)
테스트 6 〉 통과 (0.03ms, 74.3MB)
테스트 7 〉 통과 (0.01ms, 75.1MB)
테스트 8 〉 통과 (0.03ms, 76.2MB)
테스트 9 〉 통과 (0.02ms, 74.5MB)
테스트 10 〉 통과 (0.01ms, 75.9MB)

Comment

GCD (유클리드 호재법) 으로 최소공배수를 구한다음
두값을 곱한값에 최소공배수를 나누면 최대공약수가 되는걸 처음알아라따
ㄱ하자