프로그래머스(Programmers) N개의 최소공배수

🙋‍♀️ 문제 정보

문제 설명

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

제한 사항

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

입출력 예

✨ 풀이

소스 코드

function solution(arr) {
  var answer = 0;

  const gcd = (i, j) => {
    if (j === 0) {
      return i;
    }
    return gcd(j, i % j);
  };

  const lcd = (i, j) => {
    return (i * j) / gcd(i, j);
  };

  answer = arr.reduce((a, b) => lcd(a, b), 1);
  return answer;
}

결과

• 성공

해결 방법

기존의 최소공배수 문제들은 두가지 수를 받아 최소공배수를 도출하는데 해당 문제는 조금 꼬아서 N개의 수를 받아서 해당 수들의 최소공배수를 도출하는 문제이다.
최대공약수와 최소공배수를 구하는 방법은 유클리드 호제법을 사용하였고 해당 벨로그에 잘 정리되어 있다.

여러개의 수를 받아서 최소공배수를 도출하는건 arr를 돌면서 도출하면 되는데,
1. 인덱스 0번과 1번을 비교하여 최소공배수 도출(a)
2. a와 인덱스 2번을 비교하여 최소공배수 도출(b)
3. b와 인덱스 3번을 비교하여 최소공배수 도출
4. arr.length -1 인덱스 까지 반복해준다.
누적이 필요하기 때문에 reduce를 이용해서 구현해주었다.

최소공배수 같은 경우는 최대공배수가 필요하기 때문에 해당 함수를 호출했을 때 gcd를 호출하여 계산한 값을 return 해주도록 구현하였다. ✊