[프로그래머스][LEVEL2] N개의 최소공배수

# 문제 원문

 

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

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

 

# 문제 풀이

 

바로 최소 공배수를 구하는 방법과, 최대 공약수를 구한후 그걸로 최대 공배수를 구하는 방법이 있다. 바로 구하는 것 보다 최대 공약수를 구한후 그걸로 최소 공배수를 구하는게 더 효율적이다. 수학적 지식에 따라서 문제 난이도가 달라지는 문제로 보인다.

 

# 솔루션 플로우

1. 입력 받은 arr를 모두 곱한 합을 구한다.

2. 구해진 total에 최대 공약수를 나누어서 최소 공배수를 구한다.

3. 그렇게 구해진 result를 반환한다.

1. 최소 공배수 바로 구하기

function solution(arr) {
    const max = arr.reduce((result, current) => result * current);
    for (let int = Math.max(...arr); int <= max; int++) {
        if (checkNum(int)) {
            return int;
        }
    }

    function checkNum(int) {
        let result = true;
        arr.forEach((num) => {
            if (int % num !== 0) result = false;
        });
        return result;
    }
}

2. 최대 공약수 구해서 최소 공배수 구하기

function solution(arr) {
    return arr.reduce((a, b) => a * b / gcd(a, b)); // arr를 모두 곱한 수 / 최대 공약수를 작은 단위로 반복

    function gcd(a, b) { // 재귀 구조로 계속 나누어서 0 이 되는 최대 공약수 를 찾는 함수.
        return a % b ? gcd(b, a % b) : b;
    }
}