JavaScript로 자릿수 합이 같은 숫자끼리 묶어 가장 큰 그룹 개수 구하기

문제 개요

이번 포스트에서는 양의 정수 n을 유일한 인수로 받아 다음 작업을 수행하는 JavaScript 함수를 만들어 보겠습니다.

함수는 먼저 1부터 n까지의 모든 정수를 각 자릿수의 합을 기준으로 여러 그룹으로 나눕니다. 예를 들어 10은 1 + 0 = 1이므로 1과 같은 그룹에, 13은 1 + 3 = 4이므로 4와 같은 그룹에 속하게 됩니다. 그룹화가 끝나면 가장 많은 요소를 가진 그룹의 크기를 확인하고, 그 크기를 공유하는 그룹이 총 몇 개인지 반환합니다.

예시로 이해하기

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

const num = 15;

그러면 숫자들은 아래와 같이 자릿수 합을 기준으로 그룹화됩니다.

[1, 10], [2, 11], [3, 12], [4, 13], [5, 14], [6, 15], [7], [8], [9]

여기서 가장 큰 그룹은 요소를 2개씩 가진 앞쪽 여섯 개 그룹([1, 10]부터 [6, 15])입니다. 즉, 최대 크기인 2를 가진 그룹은 총 6개이므로 함수는 6을 반환합니다. 참고로 n이 한 자리 수(10 미만)라면 모든 숫자가 각각 독립적인 그룹을 이루므로, 최대 크기 그룹의 개수는 n 그 자체가 됩니다.

접근 방법

이 문제는 다음 세 단계로 나누어 해결할 수 있습니다.

1단계 – 자릿수 합 계산: 각 숫자에 대해 10으로 나눈 나머지(% 연산)를 누적해 더하고, 10으로 나눈 몫(Math.floor)으로 자릿수를 하나씩 줄여가며 모든 자릿수의 합을 구합니다.

2단계 – 그룹별 개수 집계: 객체(해시 맵)를 활용해 자릿수 합을 키로, 해당 그룹에 속한 숫자의 개수를 값으로 저장합니다.

3단계 – 최대 그룹 개수 세기: 집계가 완료되면 가장 큰 값을 찾고, 그 값과 동일한 크기를 가진 그룹이 몇 개인지 세어 반환합니다.

구현 코드

위 접근 방식을 코드로 구현하면 다음과 같습니다.

const num = 67;

const countLargestGroup = (num = 1) => {
  // 한 자리 수라면 각 숫자가 곧 독립적인 그룹이므로 n을 그대로 반환
  if (num < 10) {
    return num;
  }

  const map = {};   // 자릿수 합 -> 그룹의 요소 개수
  let maxSize = 0;  // 가장 큰 그룹의 크기
  let result = 0;   // 최대 크기를 가진 그룹의 개수

  for (let i = 1; i <= num; i++) {
    let current = i;
    let sum = 0;

    // 자릿수 합 계산
    while (current) {
      sum += current % 10;
      current = Math.floor(current / 10);
    }

    // 그룹 개수 갱신 및 최대 크기 추적
    map[sum] = (map[sum] || 0) + 1;
    maxSize = Math.max(maxSize, map[sum]);
  }

  // 최대 크기를 가진 그룹의 개수 세기
  for (const key of Object.keys(map)) {
    if (map[key] === maxSize) {
      result++;
    }
  }

  return result;
};

console.log(countLargestGroup(num));

실행 결과

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

4

num이 67일 때 자릿수 합이 6, 7, 8, 9인 네 개의 그룹이 각각 7개의 요소를 가지며, 이것이 해당 범위에서 가능한 최대 그룹 크기이기 때문입니다.

복잡도 분석

시간 복잡도는 1부터 n까지 각 숫자의 자릿수를 순회해야 하므로 O(n · log n)입니다. 여기서 log n은 숫자의 자릿수 길이에 해당합니다. 공간 복잡도는 서로 다른 자릿수 합의 개수에 비례하는데, 자릿수 합의 범위가 매우 제한적이므로 사실상 O(1)로 간주할 수 있습니다.