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

N개의 최소공배수

문제 설명

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

제한 사항

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

입출력 예

input : [2,6,8,14]
result = 168

유클리드 호제법을 접한적이 있지만, 암기는 하지 못해 일단 최소공배수를 산수에서 구하듯 구하였다.
몇가지 testcase는 돌아갔지만, 제출하기를 하자 역시 대다수의 케이스가 통과되지 않았다.

필요 개념

유클리드 호제법

1. 입력으로 두 수 m, n ( m > n) 이 들어온다.
2. n이 0이라면, m을 출력하고 알고리즘을 종료한다.
3. m이 n으로 나누어떨어지면, n을 출력하고, 알고리즘을 종료한다.
4. 그렇지 않으면 m을 n으로 나눈 나버지를 새롭게 m에 대입하고, m과 n을 바꾸고 3으로 돌아온다.

이를 코드로 구현하면 아래와 같다.

const gcd = (a, b ) => b ? gcd( b , a % b) : a;

유클리드 호제법으로 구현한 N개의 최소공배수
- 최대 공약수(gcd)를 구하여 a*b를 하면 최소공배수가 나온다.
- 최소 공배수를 그 다음 arr과 비교하여 최소공배수를 구하면 공통적인 최소공배수가 나올것이다

function solution(arr) {
    const gcd = ( a, b ) => b ? gcd(b , a % b ) : a;
    const lcm = ( a, b ) => a * b / gcd( a, b );

    return arr.reduce((a,b) => {
      const min = a < b ? a : b;
      const max = a > b ? a : b;
        return lcm(min, max);
    });
}