N개의 최소 공배수

문제 설명

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

제한 사항

• arr은 길이 1이상, 15이하인 배열입니다.

• arr의 원소는 100 이하인 자연수입니다.

입출력 예

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

이건 못푼문제다.. 자꾸 무한루프라고 나오는뎅 검색해봤다

최소공배수, 최대공약수는 유클리드의 호재법 알고리즘을 사용해야한다

(lv1에도 최소공배수, 최대공약수 문제가 있으니까 시도해보자)

n개의 숫자를 구하기 위해서는 단계별로 2개씩 비교하면서 0번과 1번의 최소공배수, 최대공약수를 구하고 다음으로는 1번과 2번의 최대공약수, 최소공배수를 구하고 이렇게 과정을 이어나가줘서 맨 마지막이 모든 값에 대한 최소 공배수임을 알 수 있다

class Solution {
    
    public int solution(int[] arr) {
        int answer = arr[0];
        
        for(int i = 1;i<arr.length;i++){
            //두 값의 최대공약수
            int gcd = gcd(answer,arr[i]);
            //두 값의 최소공배수    
            answer = answer * arr[i] / gcd;
        }
        
        return answer;
    }
    //최대공약수를 찾는 함수, 유클리드 호재
    public int gcd(int a, int b){
        int x = Math.max(a,b);
        int y = Math.min(a,b);
        
        while(x%y != 0){
            int r = x%y;
            x = y;
            y = r;
        }
        
        return y;
    }
}