139. N개의 최소공배수 Javascript

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

프로그래머스

 

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
   - n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하라
• 주어진 자료는 무엇인가?
   - n개의 숫자를 담은 배열 arr
• 조건은 무엇인가?
   - arr은 길이 1이상, 15이하인 배열입니다.
   - arr의 원소는 100 이하인 자연수입니다.

2. 계획

1. 최대 공약수를 구한다. 유클리드 호제법
   1-1. 두 수 중에서 큰 수를 작은 수로 나눈다.
   1-2. 만약 나누고 난 나머지가 0이라면 작은 수가 최대공약수이다. 
   1-2. 만약 나머지가 0이 아니라면, 작은 수를 다시 나머지로 나눈다. 
   1-3. 이를 반복해서 나머지가 0일 될 때, 그 수가 바로 두 수의 최대공약수이다. 
2. 최소공배수를 구한다. 
   2-1. (A,B의 최소공배수) = A * B / (A,B의 최대공약수)

3. 실행

• 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.

const gcd = (minNumber, maxNumber) => {
  //  두 수 중에서 큰 수를 작은 수로 나눈다.
  //   만약 나누고 난 나머지가 0 이라면 작은 수가 최대공약수이다.
  //   만약 나머지가 0 이 아니라면, 작은 수를 다시 나머지로 나눈다.
  //   이를 반복해서 나머지가 0 이 될 때, 그 수가 바로 두 수의 최대공약수이다.
  while (maxNumber !== 0) {
    n = minNumber % maxNumber;
    minNumber = maxNumber;
    maxNumber = n;
  }
  return minNumber;
}

const lcm = (minNumber, maxNumber) => {
  return (minNumber * maxNumber) / gcd(minNumber, maxNumber);
}

const solution = (arr) => {
  let answer = 1;
  for (let i = 0; i < arr.length; i++) {
    answer = lcm(answer, arr[i]);
  }

  return answer;
}

4. 반성

• 최대공약수와 최소공배수 구하는 코드를 외워야겠다.
• 최대공약수 구하는 것을 재귀로 풀어볼 수 있을 것 같다.

const gcd = (minNumber, maxNumber) => {
  //  두 수 중에서 큰 수를 작은 수로 나눈다.
  //   만약 나누고 난 나머지가 0 이라면 작은 수가 최대공약수이다.
  //   만약 나머지가 0 이 아니라면, 작은 수를 다시 나머지로 나눈다.
  //   이를 반복해서 나머지가 0 이 될 때, 그 수가 바로 두 수의 최대공약수이다.
  return minNumber % maxNumber ? gcd(maxNumber, minNumber % maxNumber) : maxNumber
}

const lcm = (minNumber, maxNumber) => {
  return (minNumber * maxNumber) / gcd(minNumber, maxNumber);
}

const solution = (arr) => {
  let answer = 1;
  for (let i = 0; i < arr.length; i++) {
    answer = lcm(answer, arr[i]);
  }

  return answer;
}