이번 튜토리얼에서는 첫 번째 인수로 숫자 n, 두 번째 인수로 숫자 배열을 받아서, 배열의 모든 요소로 나누어 떨어지는 가장 작은 n자리 수를 반환하는 JavaScript 함수를 작성해 보겠습니다. 만약 n자리 범위 안에서 조건을 만족하는 수가 존재하지 않는다면, 그 이상의 수 중에서 가장 작은 공배수를 반환하면 됩니다.
문제 이해하기
예를 들어 다음과 같은 배열이 있다고 가정해 봅시다.
const arr = [12, 4, 5, 10, 9]
이 배열의 모든 요소를 동시에 나눌 수 있는 가장 작은 수는 180입니다. 따라서 n = 2일 때(10 이상부터 탐색)와 n = 3일 때(100 이상부터 탐색) 모두 처음 만나게 되는 공배수는 180이므로, 두 경우의 출력값은 같습니다.
예제 코드
다음은 위 문제를 해결하는 전체 코드입니다.
const arr = [12, 4, 5, 10, 9];
const num1 = 2;
const num2 = 3;
// num이 arr의 모든 요소로 나누어 떨어지는지 확인
const allDivides = (arr, num) => arr.every(el => num % el === 0);
// 가장 작은 n자리 수부터 차례대로 탐색
const smallestMultiple = (arr, num) => {
let smallestN = Math.pow(10, num - 1);
while (!allDivides(arr, smallestN)) {
smallestN++;
}
return smallestN;
};
console.log(smallestMultiple(arr, num1));
console.log(smallestMultiple(arr, num2));
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
180 180
코드 동작 원리
- allDivides() 함수: 배열 메서드
every()를 활용해, 주어진 숫자가 배열의 모든 요소로 나누어 떨어지는지(나머지가 0인지) 한 번에 검사합니다. - 탐색 시작점 설정:
Math.pow(10, num - 1)로 가장 작은 n자리 수를 구합니다. n = 2라면 10부터, n = 3이라면 100부터 탐색을 시작합니다. - while 반복문: 조건을 만족하는 수를 발견할 때까지 후보 값을 1씩 증가시키며 확인한 뒤, 최종 결과를 반환합니다.
성능 개선: 최소공배수(LCM) 활용하기
1씩 증가시키며 탐색하는 방식은 직관적이지만, 배열의 값이 크거나 공배수가 매우 클 경우에는 비효율적일 수 있습니다. 최대공약수(GCD)를 이용해 배열 전체의 최소공배수(LCM)를 미리 계산하면 반복 탐색 없이 곧바로 정답을 구할 수 있습니다.
const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));
const lcm = (a, b) => (a * b) / gcd(a, b);
const smallestMultipleLCM = (arr, num) => {
// 배열 전체의 최소공배수를 한 번에 계산
const totalLcm = arr.reduce((acc, cur) => lcm(acc, cur));
// n자리 최솟값 이상인 totalLcm의 배수를 바로 산출
const start = Math.pow(10, num - 1);
return Math.ceil(start / totalLcm) * totalLcm;
};
console.log(smallestMultipleLCM([12, 4, 5, 10, 9], 2)); // 180
console.log(smallestMultipleLCM([12, 4, 5, 10, 9], 3)); // 180
이 방식은 후보 숫자를 하나하나 확인하지 않으므로, 입력 배열이 크거나 자릿수가 커져도 짧은 시간 안에 결과를 얻을 수 있다는 장점이 있습니다.