[프로그래머스/Javascript] Lv.2 N개의 최소공배수

https://school.programmers.co.kr/learn/courses/30/lessons/12953

프로그래머스

 

 

✓ 문제

 

숫자 배열(n)을 받아서 숫자들의 최소공배수 계산

 

 

✓ 풀이과정

 

처음 풀이했던 과정은 아래와 같습니다

 

1. 숫자 배열(n)을 오름차순으로 정렬해서 가장 큰 값(max)을 구하고 이를 제외한 새로운 배열(newArr) 생성

2. max 값의 배수(num)를 돌면서 남은 숫자들이 나누어 떨어지는지 확인

3. 모든 값이 나누어 떨어졌을 때만 모든 수의 최소공배수라고 판단하여 해당 값을 반환

 

function solution(arr) {
  let newArr = arr.sort((a, b) => a - b);
  let max = newArr.pop();
  let num;

  for (let i = 1; ; i++) {
    num = max * i;
    let find = true;

    for (let j = 0; j < newArr.length; j++) {
      if (num % newArr[j] !== 0) {
        find = false;
        break;
      }
    }

    if (find) break;
  }

  return num;
}

 

풀 때는 가장 큰 수를 기준으로 횟수를 줄여서 효율적인 방법이라고 생각했지만

LCM = (a * b) / GCD 라는 점과 GCD를 유클리드 호제법을 이용해서 계산한다면 더 효율적인 방법으로 해결할 수 있었습니다

 

 

최대공약수/최소공배수와 유클리드 호제법 ↓

[코딩테스트/Javascript] 최대공약수(GCD)/최소공배수(LCM)와 유클리드 호제법

 

 

1. 배열의 앞에서부터 두 수의 최대공약수를 이용해서 최소공배수를 구한다

2. 구한 최소공배수와 다음 수를 다시 연산하여 하나의 값이 남을 때까지 반복하며 최종 값을 반환

 

두 수의 연산 결과를 다음 연산의 입력으로 사용하는 누적 계산을 reduce로 구현했습니다

 

 

✓ 최종코드

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

  return arr.reduce((acc, cur) => lcm(acc, cur));
}