JavaScript로 배열의 모든 요소를 나누어 떨어지게 하는 가장 작은 n자리 수 찾기

문제 개요

첫 번째 인수로 숫자 n을, 두 번째 인수로 숫자 배열을 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 배열에 포함된 모든 요소의 배수가 되는, 즉 모든 요소로 나누어 떨어지는 가장 작은 n자리 수를 반환해야 합니다.

만약 n자리 범위 안에서 조건을 만족하는 수가 존재하지 않는다면, 자릿수와 관계없이 조건을 만족하는 가장 작은 수를 반환하면 됩니다.

예시

배열이 다음과 같다고 가정해 보겠습니다.

const arr = [12, 4, 5, 10, 9]

n = 2와 n = 3 두 경우 모두 출력 결과는 다음과 같습니다.

출력 결과

180

이 배열 요소들의 최소공배수(LCM)는 180입니다. 따라서 두 자리 수 중에서는 조건을 만족하는 수가 없으며, 180이 곧 가장 작은 공배수가 됩니다. 그래서 n = 2일 때와 n = 3일 때 모두 결과가 180로 동일하게 나오는 것입니다.

코드 구현

이 함수의 전체 코드는 다음과 같습니다.

const arr = [12, 4, 5, 10, 9]
const num1 = 2;
const num2 = 3;

// num이 배열의 모든 요소로 나누어 떨어지는지 확인
const allDivides = (arr, num) => arr.every(el => num % el === 0);

// 가장 작은 n자리 수부터 시작해 조건을 만족할 때까지 1씩 증가
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() 메서드를 활용해 주어진 수가 배열의 모든 요소로 나누어 떨어지는지 검사합니다. 단 하나의 요소라도 나누어 떨어지지 않으면 false를 반환합니다.

smallestMultiple 함수는 n자리 수의 최솟값인 10의 (n-1)제곱부터 탐색을 시작합니다. 조건을 만족하는 수를 찾을 때까지 1씩 값을 증가시키며, n자리 범위 내에서 답을 찾지 못하더라도 반복문은 멈추지 않고 계속 진행됩니다. 그 결과 자릿수가 늘어나더라도 조건을 만족하는 가장 작은 수가 최종적으로 반환됩니다.

성능 개선 팁

위 방식은 1씩 증가시키며 탐색하기 때문에 값이 커지면 비효율적일 수 있습니다. 유클리드 호제법으로 구한 최대공약수(GCD)를 이용해 배열 전체의 최소공배수(LCM)를 미리 계산해 두면, LCM의 배수만 확인하면 되므로 훨씬 빠르게 정답을 구할 수 있습니다.