[프로그래머스] n개의 최소공배수 (Lv 2) - javascript

📝 문제

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

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

🤔 풀이

1차 풀이  (미통과)

function solution(arr) {
    // 배열 오름차순 정렬
    arr.sort((a,b) => a - b);

    // max = 제일 큰 숫자 pop해서 변수 할당
    let max = arr.pop();
    let temp = max;

    // 반복문 max배수 중, arr의 모든 요소로 나누어 떨어지는 수 return
    while(true) {

        for(let i = 0; i < arr.length; i++) {
            if(max % arr[i]) break;
            if(i === arr.length - 1) return temp;
        }
        temp += max; 
    }
}

 
유클리드 호제법을 사용하지 않고 간단히 해결할 수 있을 줄 알았는데, 아니었다.
실행시간 초과로 통과하지 못했다.

 

2차 풀이

// 최대공약수
function max(i,j) {
    let k = i % j;
    if(!k) return j;
    return max(j, k);
}

// 최소공배수
function min(i,j) {
    return i*j / max(i,j);
}

function solution(arr) {
    let answer = 1;

    for(let i = 0; i < arr.length; i++) {
        answer = min(answer, arr[i]);
    }
    return answer;
}

 
유클리드 호제법을 이용해서 최대공약수, 최소공배수를 구하는 함수를 만들어주고 for문으로 배열을 순회하며 적용해줬다.

앞으로 최대공약수 or 최소공배수 관련 문제가 나오면 고민하지 말고 바로 유클리드 호제법을 적용해야겠다.

 

• 정확도 테스트 결과

 

🔑 모범 풀이

function solution(arr) {

    let value = arr[0];
    
    for(let i = 1; i < arr.length; i++) {
        value = value * arr[i] / check(value, arr[i]);
    }
    
    return value;
    
    function check(max,min) {
        let e = max % min;
        if(!e) return min;
        return check(min,e);
    }
}

 

유클리드 호제법으로 최소공약수를 구할 때 굳이 큰 수, 작은 수 나누지 않아도 된다.

유클리드 호제법 관련해서 따로 글을 작성했다.

 

[알고리즘] 최대공약수와 최소공배수 - javascript

 

• 정확도 테스트 결과

 

---

참고

kyun2da.github.io//