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

N개의 최소공배수

❓ 문제설명

두 수의 최소공배수(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

💡 풀이

function solution(arr) {
  // 내 풀이
  // 소인수 분해하여 최소 공배수 구하기
  const sosu = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]

  let answer = 1
  sosu.forEach(s => {
    let count = 0
    arr.forEach(a => {
      let subCount = 0
      while(a % s === 0) {
        subCount++
        a /= s
      }
      count = count < subCount ? subCount : count
    })
    answer *= s ** count
  })

  return answer

  // 다른사람 풀이 참고
  // 3개 이상의 최소공배수 구할 때는 순차적으로 2개의 최소공배수를 구한 후 그 수와 다음 수의 최소공배수를 구하면 된다.
  return arr.reduce((acc, cur) => {
    const gcd = (x, y) => {
      return (x % y === 0) ? y : gcd(y, x % y)
    }

    return acc * cur / gcd(acc, cur)
  })
}

📝 해설

arr 의 원소는 100이하의 자연수이기 때문에 소인수 분해로 나올 수 있는 최대의 소수까지 sosu 라는 변수로 만들고 실제 소인수분해 하듯 전체 배열을 돌며 최소공배수를 계산하였다.

 

이 후 다른사람의 풀이를 보니 3항 이상의 소인수 분해는 순차적으로 2항의 최소공배수를 구하고 이후에 하나씩 추가하며 최소공배수를 구하는 것으로 풀 수 있다는 것을 알았다. 위에 풀이는 이러한 점을 이용하여 재귀함수로 배열을 돌며 최소공배수를 계속 구해나가는 방식이다.