[알고리즘/자바스크립트] 재귀를 이용한 "음이 아닌 정수의 자릿수근" 구하기 (Sum of Digits / Digital Root)

-해당 문제는 codewars사이트의 level6 문제입니다. (1~8단계 중 8단계가 가장 쉬운 레벨)-

 

 

[문제] In this kata, you must create a digital root function. A digital root is the recursive sum of all the digits in a number. Given n, take the sum of the digits of n. If that value has more than one digit, continue reducing in this way until a single-digit number is produced. This is only applicable to the natural numbers. Here's how it works:

 

digital_root(16)
=> 1 + 6
=> 7

digital_root(942)
=> 9 + 4 + 2
=> 15 ...
=> 1 + 5
=> 6

digital_root(132189)
=> 1 + 3 + 2 + 1 + 8 + 9
=> 24 ...
=> 2 + 4
=> 6

digital_root(493193)
=> 4 + 9 + 3 + 1 + 9 + 3
=> 29 ...
=> 2 + 9
=> 11 ...
=> 1 + 1
=> 2

 

[문제 해석] 숫자를 인자로 주었을 때, 해당 숫자의 digital root를 구하는 문제이다. digital root가 무슨 뜻인지 몰라서 구글에 찾아보니 이렇게 나온다.

 

"음이 아닌 정수의 자릿수근 (영어: digital root, 반복적 자릿수합(repeated digital sum)이라고도 함)"

"자릿수를 더하는 과정을 방금 구한 그 값의 자릿수합에서 자릿수합을 구하도록 반복해서 얻어지는 (한 자리) 값이다."

 

항상 느끼는거지만 영어보다 한글이 더 어렵게 느껴질 때가 있다;; 그냥 쉽게 풀이해보자면 어떤 숫자가 주어지면 그 숫자를 하나하나 쪼개서 더한 값이 한 자리수가 될 때까지 계속 더하여 얻어지는 값이다. 예를 들어서 942의 digital root를 구하려면 9 + 4 + 2를 한다. 15가 계산되면 15를 또 쪼개서 1 + 5를 한다. 한 자리 수인 6이 출력되었으므로 6이 942의 digital root이다.

 

 

---

 

 

 

이번 문제도 재귀로 풀어보려고 한다. 

재귀를 쓰는 게 좀 익숙치가 않은데 자꾸 사용하다 보면 좀 감이 잡히겠지...

일단 가장 첫 번째로 생각한 방법은 이렇다.

 

 

1. 먼저 숫자를 하나 하나 쪼개야하므로 일단 string 형태로 변환한다. (942 => '942')

2. split 함수로 숫자를 쪼개서 배열로 만든다. (942 => ['9', '4', '2'])

3. 배열 요소를 모두 누적해서 더한다. (9 + 4 + 2를 한다.)

4. 더한 값이 10 미만이면 더한 값을 리턴하고 10 이상이면 재귀 호출한다.

 

function digital_root (n) {
  let arr = (n + '').split('');
  let sum = arr.reduce((ac, cv) => {
    return ac += Number(cv);
  }, 0);
  
  if (sum > 9) {
    return digital_root(sum);
  } else {
    return sum;
  }
}

 

reduce() 함수를 사용하여 누적 연산을 할 때 주의해야할 점은,

반드시 초기값을 0으로 세팅해야한다는 점이다. (여기서 10분 헤맸다ㅋㅋ)

 

하여튼 위 코드로 문제를 통과하였다. 짝짝짝.

 

 

 

 

이제 다른 사람의 풀이를 대충 훑어보다가 마음에 드는 풀이가 있어서 가져왔다.

나는 숫자를 string으로 변환한 후 누적해서 더하는 연산을 하기 위해선

무조건 배열로 변환을 해야한다고 생각했는데,

배열로 변환하지 않고도 숫자를 더할 수 있는 방법이 있다는 걸 알게 되었다.

 

function digital_root (n) {
  if (n < 10) {
    return n;
  }
  for (var i = 0, sum = 0, n = (n + ''); i < n.length; i++) {
    sum += Number(n[i]);
  }
  return digital_root(sum);
}

 

그리고 제일 신박했던 점은 변수 i랑 sum, n을 모두 for문 안에서 선언했다는 점인데,

저렇게 쓰는 것이 더 좋은지 밖에다 쓰는 것이 좋은지 잘 모르겠다.

 

뭔가 for문의 조건 부분이 너무 길어지는 것 같아서 밖으로 빼는 것이 가독성이 낫지 않을까 싶긴 하다.

 

 

위 코드는 n이 10보다 작은지 먼저 판별한 후 누적 연산을 진행하는 데, 이게 맞는 것 같다.

내 코드는 n이 10보다 작은 값이어도 일단 string으로 변환해서 불필요한 연산을 하기 때문이다.