[구현] 프로그래머스 'N개의 최소공배수' - js

1. 문제

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

프로그래머스

2. 코드

내가 짠 코드) 테케만 통과하고 채점에서는 모두 틀렸다고 나왔다.. 이게 될까? 하고 해본건데 역시 안되네 ㅋㅋㅋ

function solution(arr) {
    let answer = arr[arr.length-1];
    
    for(let i=0;i<arr.length-1;i++){
        let temp = arr.filter(el => answer%el !== 0);
        if(temp.length) answer *= arr[i];
        else break;
    }
    
    return answer;
}

방식 1)

function solution(arr) {
    // 최소 공배수를 구하는 것이므로 0번째 요소에 +1씩 증가하는 숫자를 계속 곱해준다.
    let n = 1, flag = false;
    while(!flag)
    {
        n++;
        for(let i = 1; i < arr.length; ++i){
            if((arr[0] * n) % arr[i]  === 0){
                flag = true;
            } else {
                flag = false;
                break;
            }
        }
    }

    return arr[0] * n;
}

 

방식 2  : 유클리드 호제법 이용하는 방식)

function solution(arr) {
 // 최소 공배수 : 값들의 전체 곱/최대공약수
  return arr.reduce((a, b) => (a * b) / getGcd(a, b));
}

// 최대 공약수
function getGcd(a, b) {
  if (b === 0) return a;
  return getGcd(b, a % b);
}

유클리드 호제법을 이용하여 최소 공배수, 최대 공약수를 구하면 매우 효율적이다. 구한 최대 공약수를 사용하여 최소 공배수를 쉽게 구해낼 수 있다.

최대 공약수 알고리즘은 이 링크를 들어가 쭉 읽어보면 쉽게 이해할 수 있다.

https://imkh.dev/algorithm-gcd-lcm/

최소공배수와 최대공약수 알고리즘 (유클리드 호제법) | imkh.dev

 

복기

5/24