Lv2)JS - N개의 최소공배수

문제링크

코딩테스트 연습 - N개의 최소공배수

느낀점

분명히 최소공배수를 푸는 방법을 학습했었는데 기억이 나지 않고 내가 풀었고 블로그에 기록을 했지만 안보고 풀고 싶었다.

분명히 while문으로 풀면 풀 수 있을것이라고 생각했는데 break가 되지 않고..... 그래서 재귀를 이용해서 문제를 풀었는데....

테스트 케이스 1개가 런타임 오류가 발생... 결국 다른 분들의 풀이를 참고 했다.

 

유클리드 호제법
두 양의 정수 a,b(a>b)에 대하여 a를 b로 나눈 나머지가 r일 때,
a와 b의 최대공약수는 b와 r의 최대공약수와 같다

 

계속 반복해서 0이 나올때까지 나누면 그 수가 바로 최대공약수라는 뜻이다.

최소 공배수는 두 수 a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 것과 같다.

 

내가 푼 방법

function solution(arr) {
    let max = Math.max(...arr);
    function resol(arr1, max1) {
        let newArr = arr1.filter((el) => {
            if (max % el !== 0) {
                max += max1;
            } else {
                return el
            }
        });
        if (newArr.length === arr.length) {
            return max;
        } else {
            resol(arr1, max1)
        }
    }

    resol(arr, max);
    return max;
}

다른 방법

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));
}

 

reference

imkh.dev님 블로그

개발전용차선님 블로그