N개의 최소 공배수

문제설명

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

제한사항

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

입출력 예

풀이

// N개 수의 곱 / N개의 최대 공약수 => N개의 최소공배수
// 유클리드 호제법으로 최대공약수 구하기

function solution(arr) {
    
    function gcd(a, b){
        if (b === 0) {return a;}
        return gcd(b, a % b);
    }
    return arr.reduce((acc, cur) => {
        return (acc * cur) / (gcd(acc, cur));
    })
}

해설

두 수의 곱 / 두 수의 최대공약수 = 두 수의 최소공배수 인 것을 활용해서 풀이

1. 최대공약수 구하는 함수(유클리드 호제법)

• 유클리드 호제법을 통해 12345와 123의 최대 공약수를 구하는 풀이
  

// 최대 공약수를 구하는 함수
fuction gcd(a, b){
  if (b === 0) return a;
  return gcd(b, a % b);
}

즉, 재귀를 돌면서 a % b 의 값이 0이 되는 순간의 a를 return 하는 구조입니다
a와 b의 대소관계는 크게 신경 안써도 되는 함수입니다
예를 들어 a = 5, b = 30인 경우에는
5 % 30 = 5이기 때문에 다음 재귀에서return gcd(30, 5)로 들어가게 됩니다

2. reduce() 메서드를 활용 arr에 들어오는 모든 수의 최소공배수 구하기

입출력 예시 [2, 6, 8, 14]를 이용해 설명해보겠습니다

 return arr.reduce((acc, cur) => {
        (acc * cur) / (gcd(acc, cur));

위 코드 에서 acc값을 따로 지정해주지 않았으므로
초기 acc값에는 arr[0]이 들어갑니다. 순서대로 설명해보자면
1) arr[0] * arr[1] / gcd(arr[0], arr[1])
즉, 2와 6의 곱을 2와 6의 최대공약수로 나눠서 최소공배수를 구합니다
➡️ 2와 6의 최소공배수 :6이 축적값인 acc로 들어갑니다

2) acc * arr[2] / gcd(acc, arr[2])
6과 8의 최소공배수 : 24

3) acc * arr[3] / gcd(acc, arr[3])
24와 14의 최소공배수 : 168

최종적으로 [2, 6, 8, 14] 의 최소 공배수 168을 구했습니다