알고리즘 81번 - N개의 최소공배수

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

JS

문제

문제 설명

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

제한 사항

arr은 길이 1이상, 15이하인 배열입니다.

arr의 원소는 100 이하인 자연수입니다.

입출력 예

arr	result
[2,6,8,14]	168
[1,2,3]	6

 

 

---

계획

모든 수의 약수를 찾고 최소 공배수를 반환하

---

참고, 풀이

지수를 이용하여 공배수 찾기

1.  숫자를 소인수분해 해서 지수구하기

2.공통이든 아니든 모든 소수를 다 쓰되, 공통인 건 지수가 큰 걸 사용

---

답

function primeFactorization(n) {
    let factors = {};
    let divisor = 2;
    
    while (n > 1) {
        while (n % divisor === 0) {
            factors[divisor] = (factors[divisor] || 0) + 1;
            n /= divisor;
        }
        divisor++;
    }
    
    return factors;
}

const solution = (arr) => {
    let lcmFactors = {};

    for (let num of arr) {
        let factors = primeFactorization(num);

        for (let factor in factors) {
            lcmFactors[factor] = Math.max(lcmFactors[factor] || 0, factors[factor]);
        }
    }

    // 최소공배수 계산
    let lcm = 1;
    for (let factor in lcmFactors) {
        lcm *= Math.pow(parseInt(factor), lcmFactors[factor]);
    }

    return lcm;
};

코드 간략화하기

const primeFactorization = (n, f = {}, d = 2) => {
  while (n > 1) (n % d ? d++ : (f[d] = (f[d] || 0) + 1, n /= d));
  return f;
};

const solution = (arr) => arr.reduce((lcmFactors, num) => {
  for (let [factor, exp] of Object.entries(primeFactorization(num))) {
    lcmFactors[factor] = Math.max(lcmFactors[factor] || 0, exp);
  }
  return lcmFactors;
}, {}).entries().reduce((lcm, [f, e]) => lcm * f ** e, 1);

다른사람 답

function solution(arr) {
    return arr.reduce((a, b) => (a * b) / gcd(a, b));
}

function gcd(a, b) {
    return b ? gcd(b, a % b) : a;
}

설명

1. gcd(a, b): 유클리드 알고리즘을 사용하여 최대공약수(GCD)를 계산합니다.
2. reduce(): 배열의 모든 요소에 대해 (a * b) / gcd(a, b) 연산을 적용하여 최소공배수(LCM)를 구합니다.
3. 시간 복잡도: O(nlog⁡M)O(n \log M)O(nlogM) (M은 최대 숫자 크기, 100 이하)
4. 공간 복잡도: O(1)O(1)O(1) (추가 배열 없이 상수 공간 사용)

 

function solution(arr) {
    return arr.reduce((acc, cur) => {
        const recursive = (min, max) =>{
          return (min % max) === 0 ? max : recursive(max, min % max);
        }

        let max = 0;
        return acc*cur / recursive(acc,cur);
    });
}

---

참고

최소 공배수 구하기 - https://mathbang.net/204

js에서 최소 공배수 구현 -

https://velog.io/@devjade/JavaScript%EB%A1%9C-%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98GCD-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98LCM-%EA%B5%AC%ED%95%98%EA%B8%B0