28. N개의 최소공배수 (Level 3, JavaScript)

N개의 최소공배수 (Level 3)

문제

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다.

예를 들어 2와 7의 최소공배수는 14가 됩니다.

정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다.

nlcm 함수를 통해 n개의 숫자가 입력되었을 때, 최소공배수를 반환해 주세요.

예를들어 [2,6,8,14] 가 입력된다면 168을 반환해 주면 됩니다.

풀이

function nlcm(num) {
    let res = [num[0]];
  for ( let i = 1; i < num.length; i++ ) {
    let max = 1;
    for ( let j = 2; j <= Math.min(res[i-1], num[i]); j++ ) {
          if (( res[i-1] % j == 0 ) && ( num[i] % j == 0 )) {
        if ( max < j ) { max = j } 
        }
    }
    res[i] = res[i-1]*num[i]/max
  }
  return res[res.length-1]
}

// 아래는 테스트로 출력해 보기 위한 코드입니다.
console.log(nlcm([2,6,8,14]));

꽤 오래 걸린 것 같음.. 생각하고서 쓰질않고 쓰고나서 생각해버리니까 아예 방향을 잘못잡아서 고생함.

res라는 배열에 num배열에서 순차적으로 두 수의 최대공배수를 계산해 삽입.

res[0] = num[0]

res[0],num[1] => res[1]

res[1],num[2] => res[2]

…

res[num.length-2],num[num.length-1] => 결과

이런식으로 계산을 했다.

썩 마음에 드는 코드는 아닌 것 같다.

다른 사람의 풀이

function nlcm(num) {
  return num.sort((a, b) => a - b).reduce(lcm);
}
function lcm(num1, num2){
  return (num1 * num2) / gcd(num1, num2);
}
function gcd(num1, num2){
  if(num2 == 0) return num1;
  return gcd(num2, num1%num2);
}

// 아래는 테스트로 출력해 보기 위한 코드입니다.
console.log(nlcm([2,6,8,14]));

이런식으로 풀어보려 했는데, 머리가 너무 복잡해져서 떠올리지 못해버렸다..

으렵다