[Lv.2] N개의 최소공배수

문제 설명

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

제한 사항

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

풀이

일단 문제에서 최소공배수 보자마자 유클리디안 알고리즘이 생각났다.

유클리디안 알고리즘이란 최대공약수를 기본 가정으로 한다.

두 수 a, b(a > b)에 대해 a를 b로 나눈 나머지를 r이라고 할 때, a와 b의 최대공약수는 b와 r의 최대 공약수와 같다.

이 정의를 바탕으로 직접 숫자를 대입해보면 쉽게 이해할 수 있다.

GCD(581, 322)일 때 r(나머지) = 259이다. 즉, GCD(581, 322) = GCD(322, 259)이다. 그럼 다시 GCD(322, 259)를 보면 r=63이다. GCD(581, 322) = GCD(322, 259) = GCD(259, 63)이다. 또 다시 하면 r=7이다. 따라서 GCD(581, 322) = GCD(322, 259) = GCD(259, 63) = GCD(63, 7)이다. 마지막으로 하면 r=0이다. 따라서 GCD(581, 322) = GCD(322, 259) = GCD(259, 63) = GCD(63, 7) = GCD(7, 0)이다.

이로써 581과 322의 최대공약수는 7이다.

다음으로는 최대공약수를 이용해 최소공배수를 구하는 정의가 있다.

최소공배수 = 두 자연수의 곱 / 최대공약수

여기까지 알면 이 문제는 끝이다. 위 정의들을 바탕으로 문제를 풀어 나가면 된다. 최대 공약수를 먼저 구하고 최소공배수를 구하면 된다.

여기까지는 유클리드의 호제법을 이용해 문제를 푼 것이다. 완전탐색을 이용해 풀 수도 있다. 냅다 반복돌리면서 2부터 1씩 더하면서 모든 배열의 요소들이 나누어 떨어질 때 반복을 끝내고 반환하면 된다.

통과 코드

호제법을 이용한 풀이

function solution(arr) {
  // 2와 7의 최소 공배수는 14
  // n개의 수의 최소공배수는 n개의 수들의 배수 중 공통이 되는 가장 작은 숫자
  // arr: n개의 숫자를 담은 배열
  // arr의 요소들의 최소공배수를 반환
 
  var answer = lcm(arr[0], arr[1]);
  var newArr = arr.slice(2);
  
  for (var i = 0; i < newArr.length; i++) {
    answer = lcm(answer, newArr[i]);
  }
 
  return answer;
}
 
function gcd(num1, num2) {
  var k;
  while (num2 !== 0) {
    k = num1 % num2;
    num1 = num2;
    num2 = k;
  }
  return num1;
}
 
function lcm(num1, num2) {
  return num1 * num2 / gcd(num1, num2);
}

완전탐색을 이용한 풀이

function solution(arr) {
  let count = 2;
  
  while(true){
    let check = true;
    for(let i = 0; i < arr.length; i++){
      if(count % arr[i] !== 0) {
        check = false;
        break;
      };
    }
    
    if(!check) count++;
    if(check) break;
  }
  return count;
}