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

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

 

 

 

 

내 제출

function solution(arr) {
    var answer = 0;
    let i=1;
    while(true){
				//1씩 증가하면서 모든 수의 공배수를 일일이 찾아본다.
		    //근데 1씩만 증가하면 너무 많이 검사하니까 배열의 숫자중 아무거나 선택해서 그거랑 곱해준다.
        var an=arr.reduce(function(total, val,idx, arr){
            return (i*arr[0])%val==0 ? total +1 : 0;
        },0);
        if(an==arr.length){
            answer=i*arr[0];
            break;
        }
        i++;
    }
    return answer;
}

내 방식은 먼저 배열의 아무 수를 계속해서 곱하고

그것을 배열안의 숫자들로 나눴을 때 나머지가 모두 0이면 그 값을 꺼내오는 것이다.

 

 

다른 풀이

function solution(arr) {
    return arr.reduce((acc, cur) => {
        const recursive = (min, max) =>{
          return (min % max) === 0 ? max : recursive(max, min % max);
        }

        let max = 0;
        return acc*cur / recursive(acc,cur);
    });
}

function getGcd(a, b) {
  if (b === 0) return a;
  return getGcd(b, a % b);
}

function solution(arr) {
  return arr.reduce((a, b) => (a * b) / getGcd(a, b));
}

이 방식들은 유클리드 호제법을 이용했다.

x * y / 최대공약수 = 최소공배수

진행 과정을 요약 하자면 아래와 같다.

[2,6,8,14] -> [6,8,14] -> [24, 14] -> [168](2 * 6) / 2 = 6 -> (6 * 8) / 2 = 24 -> (24 * 14) / 2 = 168

function solution(arr) {
    // 최대 공약수를 위해 내림차순으로 정렬해준다.
    arr.sort((a,b) => b - a);
    let r, m, n = 0, acc = arr[0];
    for(let i = 1; i < arr.length; ++i){
        // 유클리드 호제법으로 두 수의 최대공약수를 구한다.
        m = acc; // 큰 수
        n = arr[i]; // 작은 수
        while(0 < n){
            r = m % n;
            m = n;
            n = r;
        }
        // m은 두 수의 최대공약수, acc에 두 수의 최소공배수를 누적시킨다.
        acc = acc * arr[i] / m;
    }
    return acc;
}

이 방식은 먼저 내림차순으로 정렬한다.→ [14,8,6,2]

그다음에 acc는 가장큰 수를 저장하고

m에 acc →14

n은 그 다음 큰수를 넣는다 →8

그리고 반복문으로 두수의 최대 공약수를 구한다.

while(0 < n){ //최대공약수 구하는 공식
            r = m % n;
            m = n;
            n = r;
        }

이렇게 되면 m은 2가 된다.

그리고 acc는 accarr[i] / m을 한다 →148/2 =56 ⇒이는 최소공배수다.(유클리드 호제법)

그리고 m은 다시 56이 되고, n은 6가된다. → 656 / 2=168 → 1682/2 =168