JavaScript로 연속된 n자리 숫자의 최대 곱 구하는 방법

이번 글에서는 두 개의 숫자를 인수로 받는 JavaScript 함수를 작성해 보겠습니다. 첫 번째 인수를 m, 두 번째 인수를 n이라고 부르겠습니다.

첫 번째 숫자 m은 일반적으로 여러 자릿수로 이루어진 숫자이며, 두 번째 숫자 n은 항상 m의 자릿수보다 작은 값입니다.

함수의 목표는 m에서 연속된 n개의 숫자를 추출했을 때 그 곱이 가장 커지는 조합을 찾아 해당 곱을 반환하는 것입니다.

문제 예시

예를 들어 입력값이 다음과 같다고 가정해 보겠습니다.

const m = 65467586;
const n = 3;

이때 기대되는 출력 결과는 다음과 같습니다.

const output = 280;

그 이유는 7 × 5 × 8 = 280으로, 이 숫자에서 연속된 세 자리 숫자의 곱 중 가장 큰 값이기 때문입니다.

슬라이딩 윈도우 방식의 접근

가장 효율적인 방법은 슬라이딩 윈도우(Sliding Window) 기법을 활용하는 것입니다. 처음 n개의 숫자 곱을 계산한 뒤, 창을 한 칸씩 오른쪽으로 이동하면서 빠져나가는 숫자로 나누고 새로 들어오는 숫자를 곱하면 됩니다. 이렇게 하면 매번 전체 곱을 다시 계산하지 않아도 되므로 시간 복잡도를 O(m의 자릿수) 수준으로 유지할 수 있습니다.

구현 코드

다음은 위 로직을 구현한 코드입니다.

const m = 65467586;
const n = 3;
const largestProductOfContinuousDigits = (m, n) => {
   const str = String(m);
   if(n > str.length){
      return 0;
   };
   let max = -Infinity;
   let temp = 1;
   for(let i = 0; i < n; i++){
      temp *= +(str[i]);
   };
   max = temp;
   for(i = 0; i < str.length - n; i++){
      temp = (temp / (+str[i])) * (+str[i + n]);
      max = Math.max(temp, max);
   };
   return max;
}
console.log(largestProductOfContinuousDigits(m, n));

코드 동작 원리

코드의 흐름을 단계별로 살펴보면 다음과 같습니다.

1단계: 숫자 m을 문자열로 변환하여 각 자릿수에 쉽게 접근할 수 있도록 합니다.

2단계: n이 문자열 길이보다 크다면 연속된 n개의 숫자를 만들 수 없으므로 0을 반환합니다.

3단계: 첫 번째 윈도우, 즉 앞에서부터 n개의 숫자 곱을 계산하여 초기 최댓값으로 설정합니다.

4단계: 윈도우를 한 칸씩 이동시키면서 이전 곱에서 빠지는 숫자를 나누고 새로 들어오는 숫자를 곱합니다. 각 단계마다 Math.max()로 현재까지의 최댓값을 갱신합니다.

출력 결과

위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.

280

이처럼 슬라이딩 윈도우 기법을 사용하면 반복 계산 없이 효율적으로 연속된 숫자의 최대 곱을 구할 수 있습니다.