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

시도했던 방법 & 결과

function solution(arr) {
    // 최대공약수 구하기
    let min = Math.min(...arr);
    let divisor = min
    let gcd = 1;
    
    for (divisor; divisor > 0; divisor--) {
        if (arr.every(num => num % divisor === 0)) {
            gcd = divisor;
        } break
    }
    // 최소공배수 구하기
    let lcm = 1
    arr.forEach((num) => lcm *= num / gcd)
    lcm *= gcd
    
    return lcm
}

최소공배수를 구하려면 최대공약수를 알아야 하기 때문에 최대공약수부터 구했다. 최대공약수는 배열의 최솟값보다 작거나 같을 수밖에 없다. 그래서 최솟값을 변수 divisor에 복사하고 divisor을 하나씩 감소시키면서 모든 숫자의 약수가 되는 divisor를 찾았다. 이 divisor는 자동으로 최대공약수가 된다.

그리고 숫자를 최대공약수로 나눈 몫끼리 곱한 후 마지막으로 최대공약수를 곱했다. 테스트 케이스는 통과했지만 실패했다.

문제점

최소공배수를 구하는 방법이 잘못되었다. 예를 들어, [3, 6, 18]의 최소공배수는 18이지만 위 로직대로 하면 36이 나온다. 모든 수의 최대공약수로 나눈 후에도 몫이 1이 아닌 나머지 수들을 그들의 최대공약수로 나눌 수 있다면 나눠야 하기 때문이다.

해결

function solution(arr) {
    // 두 수의 최소공배수 구하기
    function getLcm(a, b) {
        let min = Math.min(a, b);
        let gcd = min;

        for (gcd; gcd > 0; gcd--) {
            if (a % gcd === 0 && b % gcd === 0) {
                break;
            }
        }
        return (a * b) / gcd;
	}

	for (let i = 0; i < arr.length -1; i++) {
		arr[i+1] = getLcm(arr[i], arr[i+1])
	}
    return arr[arr.length -1]
}

두 수의 최소공배수를 구하는 함수를 만든다. 두 수의 최소공배수는 두 수를 곱한 값에 최대공약수를 나눈 값과 같다는 성질을 이용했다. 그리고 배열의 앞에서부터 차례대로 최소공배수를 구하는 함수를 적용한 뒤 최종값을 반환한다.