[JS] N개의 최소공배수

 

 

난이도: Lv.2

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

프로그래머스

 

 

알고리즘

바로 다음에 있는 수와 최소공배수를 구하는 과정을 배열의 끝에 도달할때까지 반복한다.

최소공배수는 소인수분해 하지않고 초등학생 시절 배웠던 것처럼 덧셈으로 구한다. 예시로 2와 3의 최소공배수를 구해보자.

(2, 3) → (4, 3) → (4, 6) → (6, 6) 으로 최소공배수 6을 구한다. 두 수를 비교해서 더 작은 수만 더해준다.

 

 

코드

function solution(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        num1 = arr[i];
        num2 = arr[i + 1];
        while (num1 !== num2) {
            if (num1 > num2) { num2 += arr[i + 1]; }
            else { num1 += arr[i]; }
        }
        arr[i + 1] = num1;
    }

    return arr[arr.length - 1];
}

 

 

주저리

배열안에 있는 모든 수를 소인수분해 해놓고 최소공배수랑 연관성을 찾고싶었는데 못찾고 포기했다. 최소공배수 구하는 방법(알고리즘 검색한거 아님) 검색했는데 배수들 나열해놓고 구하는거 보고 깨달았다. Math에 내장함수가 있는 것 같긴한데 존재하리라고 전혀 상상도 못했다.