[JS][N개의 최소공배수]

N개의 최소공배수

문제설명

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

제한 사항

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

유클리드 알고리즘 (최소 공배수 구하는 방법 )

유클리드 알고리즘을 사용하여 최대공약수를 찾는 방법은 다음과 같습니다:

1. 두 수 (a)와 (b)에 대해, (a)가 (b)보다 크도록 정렬합니다. (만약 그렇지 않다면 두 수를 교환합니다.)
2. (a)를 (b)로 나눕니다. 그리고 나머지를 구합니다.
3. 만약 나머지가 0이라면, (b)는 최대공약수입니다.
4. 만약 나머지가 0이 아니라면, (b)를 (a)로 설정하고, 나머지를 (b)로 설정한 후 2단계로 돌아갑니다.

1,2,3,4를 해결 해주는 코드는 다음과 같다.

최대 공약수 구하기

function gcd(a,b){
    while(b!==0){
      [a,b] = [b, a%b];
    }
    return a;
}

최소 공배수 구하기

function lcm(a,b){
    return (a*b)/gcd(a,b);
}

활용

console.log(lcm(a,b));

이런식으로 활용해주면 되는데, 아시다시피 이 코드는 두개의 수를 고려할 때만 해당이 된다!

숫자 여러개의 최소공배수를 구하려면?

입력받는 숫자배열을 원소하나씩 순차적으로 비교해주면 될 것이다.

출처:네이버 - 숫자 여러개의 최대공약수 구하는 방법

최소 공배수를 구하면서 계속해서 다음 원소와 비교

이렇게 std를 1로 지정해서 처음인자로, 이후 계속해서 업데이트해주는 for문

function solution(arr) {
    let std = 1 ;
    for(let i = 0 ; i< arr.length;i++){
        std = lcm(std,arr[i]);
    }
        return std;
    }

최종 코드

//최대 공약수 구하기
function gcd(a,b){
    while(b!==0){
      [a,b] = [b, a%b];
    }
    return a;
}

//최소 공배수 구하기
function lcm(a,b){
    return (a*b)/gcd(a,b);
}

//최소 공배수 구하면서 계속해서 다음원소와 비교
function solution(arr) {
    let std = 1 ;
    for(let i = 0 ; i< arr.length;i++){
        std = lcm(std,arr[i]);
    }
        return std;
    }