[JS] n개의 최소공배수

문제 설명

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

 

문제 풀이

const gcd = (a,b) => {
   if(b === 0){
        return a;
    }else if(a%b === 0){
        return b;
    }else{
        return gcd(b, a%b);
    };
}

const lcm = (a,b) => {
    return (a*b) / gcd(a,b);
};

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

 

1. n개 이상의 수에서 최소공배수를 구하는 과정

let x = 첫번째 수와 두번째 수의 최소공배수
x = x와 세번째 수의 최소공배수
…
x = x와 n번째 수의 최소공배수

 

2. 최소공배수를 구하려면

두 수의 곱 / 최대공약수

 

3. 최대공약수를 구하려면 => 유클리드 호제법

두개의 숫자 a, b가 존재함. ( a > b)
1. b가 0이면 a 출력 후 종료
2. a가 b로 나누어 떨어지면, b 출력 후 종료
3. 나누어 떨어지지 않으면, a = a % b 대입하고 a와 b를 바꾼다.
4. 이 과정을 반복한다.

 

 

참고블로그

https://velog.io/@jan/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-N%EA%B0%9C%EC%9D%98-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98-JavaScript

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