문제 설명
두 수의 최소공배수(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 |
문제풀이
💡 문제풀이 과정
최소공배수(Least Common Multiple, LCM)을 구하기 위해최대공약수(Greatest Common Divisor, GCD)를 먼저 구하기로 한다.- 두 정수의 최대공약수를 구할 때는 소인수분해를 이용하거나, 나눗셈을 이용하는 방법이 있었다. (다음 예제 참고)
// 1. 소인수분해 이용하는 법 12 = 2² * 3, 30 = 2 * 3 * 5 gcd(12, 30) = 2 * 3 = 6 // 각 수를 소인수분해 한다. // 공통인 소인수 중에서 거듭제곱의 지수가 같으면 그대로, // 다르면 작은 것을 선택하여 모두 곱한다. // 2. 나눗셈 이용하는 법 2 ) 12 30 ¯¯¯¯¯¯¯¯ 3 ) 6 15 ¯¯¯¯¯¯¯¯ 2 5 gcd(12, 30) = 2 * 3 = 6 // 두 수의 공통인 소인수로 각 수를 나눈다. // 공통인 소인수를 왼쪽에 표시하고 몫은 아래 식으로 내린다. // 몫이 서로소가 될 때까지 계속 나눈다. (2, 5는 서로소) // 공통으로 나온 소인수를 모두 곱한다. // cf. 서로소는 두 정수 a,b의 최대공약수가 1일 때 a와 b는 서로소라고 한다. // cf. 수가 커지면 나눗셈보다는 소인수분해를 이용하는 것이 효과적이다.
- 세 개 이상의 정수의 최대공약수를 구하기 위해 다음과 같은 예제를 참고한다.
// 1. 최대공약수(GCD) // 세 정수 a, b, c의 최대공약수 = gcd(a, b, c) gcd(a, b, c) = gcd(gcd(a, b), c) = gcd(a, c) // a = 6, b = 12, c = 21일 때, 세 정수를 소인수분해하면 다음과 같다. // 세 수의 최대공약수는 3이다. 6 = 2 * 3, 12 = 2² * 3, 21 = 3 * 7 // 최대공약수의 성질을 이용하여 다음과 같이 구할 수 있다. gcd(6, 12, 21) = gcd(gcd(6, 12), 21) = gcd(6, 21) = 3 // 2. 최소공배수(LCM) // 두 정수 a, b의 최소공배수 = lcm(a, b) // lcm(a, b) = 최대공약수 * (a / 최대공약수) * (b / 최대공약수) lcm(a, b) = gcd(a, b) * (a / gcd(a, b)) * (b / gcd(a, b)) // 정수가 3개 이상일 때 최소공배수 구하기 // 세 정수 a, b, c의 최소공배수 = nlcm(a, b, c) = 정수가 n개 일때 최소공배수 nlcm = [a, b, c].reduce((acc, cur) => (acc * cur) / gcd(acc, cur));
✅ 답안
function solution(arr) {
const gcd = (min, max) => {
return min % max == 0 ? max : gcd(max, min % max);
};
const nlcm = (nums) => {
return nums.reduce((a, b) => (a * b) / gcd(a, b));
};
return nlcm(arr);
}