디지털 루트란 무엇인가?
디지털 루트(digital root)는 어떤 양의 정수의 모든 자릿수를 단순히 더한 값을 의미합니다. 예를 들어 13의 디지털 루트는 1 + 3 = 4입니다.
정수 배열이 주어졌을 때, 우리는 다음 규칙에 따라 배열을 정렬해야 합니다.
- 숫자 a가 숫자 b보다 앞에 오려면, a의 디지털 루트가 b의 디지털 루트보다 작거나 같아야 합니다.
- 두 숫자의 디지털 루트가 같다면, 일반적인 크기 기준으로 더 작은 숫자가 먼저 와야 합니다.
예를 들어 4와 13은 디지털 루트가 같습니다(둘 다 4). 하지만 4 < 13이므로, 두 숫자가 모두 포함된 디지털 루트 정렬에서는 항상 4가 13보다 앞에 위치하게 됩니다.
입출력 예시
a = [13, 20, 7, 4] 인 경우,
출력 결과는 [20, 4, 13, 7] 이어야 합니다.
왜 이런 결과가 나오는지 살펴보겠습니다. 각 숫자의 자릿수 합은 다음과 같습니다.
- 20 → 2 + 0 = 2
- 13 → 1 + 3 = 4
- 4 → 4
- 7 → 7
자릿수 합이 2인 20이 가장 앞에 오고, 같은 값 4를 가진 4와 13 중에서는 더 작은 4가 먼저 옵니다. 마지막으로 7이 뒤따르게 됩니다.
구현 전략
이 문제는 두 개의 함수로 나누어 깔끔하게 해결할 수 있습니다.
- 재귀 함수(recursiveCount): 숫자의 각 자릿수를 더한 합계를 계산합니다.
- 정렬 함수(sorter): 자릿수 합을 기준으로 배열 요소들의 순서를 결정하는 비교 함수입니다.
코드 예제
const arr = [54, 23, 8, 89, 26];
const recursiveCount = (num, count = 0) => {
if(num){
return recursiveCount(Math.floor(num/10), count + num % 10);
};
return count;
};
const sorter = (a, b) => {
const countDifference = recursiveCount(a) - recursiveCount(b);
return countDifference || a - b;
};
arr.sort(sorter);
console.log(arr);
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
[ 23, 8, 26, 54, 89 ]
코드 동작 원리 상세 분석
1. recursiveCount — 자릿수 합 계산하기
recursiveCount 함수는 재귀적으로 동작합니다. 매개변수 num이 0이 아닌 동안, num % 10(마지막 자릿수)를 누적 변수 count에 더하고, Math.floor(num / 10)으로 마지막 자릿수를 제거한 값을 가지고 자기 자신을 다시 호출합니다. num이 0이 되면 지금까지 누적된 count, 즉 자릿수의 총합을 반환합니다.
2. sorter — 스마트한 비교 로직
sorter 함수는 자바스크립트의 Array.prototype.sort() 메서드에 전달되는 비교 함수입니다. 여기서 핵심은 다음 한 줄입니다.
return countDifference || a - b;
자바스크립트에서 || 연산자는 왼쪽 값이 truthy일 경우 그 값을 반환하고, falsy(여기서는 0)일 경우 오른쪽 값을 반환합니다. 따라서 두 숫자의 자릿수 합이 다르면 그 차이를 기준으로 정렬되고, 자릿수 합이 같아 차이가 0이 되면 a - b가 실행되어 일반적인 숫자 크기 순으로 정렬됩니다. 이 패턴 덕분에 별도의 if 문 없이 두 단계의 정렬 기준을 우아하게 처리할 수 있습니다.
마무리 및 성능 고려사항
이 알고리즘의 시간 복잡도는 정렬에 기반하므로 O(n log n)이며, 각 숫자의 자릿수 합 계산은 숫자의 길이에 비례하여 매우 빠르게 수행됩니다. 만약 같은 배열에서 자릿수 합을 반복적으로 조회해야 한다면, 미리 각 숫자의 자릿수 합을 Map 객체에 캐싱해 두는 최적화도 고려해 볼 수 있습니다. 재귀와 sort 비교 함수의 조합은 이처럼 다단계 정렬 조건을 처리하는 데 유용한 패턴이니, 실무에서도 자주 활용해 보시기 바랍니다.