4673번 셀프넘버

문제 : https://www.acmicpc.net/problem/4673

문제

셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다.

양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다.

예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다.

33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...

n을 d(n)의 생성자라고 한다. 위의 수열에서 33은 39의 생성자이고, 39는 51의 생성자, 51은 57의 생성자이다. 생성자가 한 개보다 많은 경우도 있다. 예를 들어, 101은 생성자가 2개(91과 100) 있다.

생성자가 없는 숫자를 셀프 넘버라고 한다. 100보다 작은 셀프 넘버는 총 13개가 있다. 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97

10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

입력

입력은 없다.

출력

10,000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다.

풀이

 let solResult = "";
// 원하는 범위까지 수열을 만드는 함수 d(n)
 function d(n, limit, array) {
   let N = String(n);
   let result = Number(n);
   if (result > limit) {
     return;
   }
   for (let i = 0; i < N.length; i++) {
     result += Number(N[i]);
   }
   array.push(result);
   d(result, limit, array);
 }

// 셀프넘버가 아닌 배열을 만들고 이를 1 ~ 범위까지의 배열과 비교
 function solution(number) {
   let array = [...Array(number)].map((a, i) => i + 1);
   let noSelfNumber = [];
   for (let i = 1; i < array.length; i++) {
     d(i, array.length, noSelfNumber);
   }
   for (let i = 0; i < array.length; i++) {
     if (noSelfNumber.indexOf(array[i]) === -1) {
       solResult += array[i].toString();
       solResult += "\n";
     }
   }
   console.log(solResult);
 }
 solution(10000);

처음으로 생각했던 풀이법이다. 제한 범위까지 계속 호출되면서 수열을 만드는 d(n) 함수를 먼저 선언하였고 이를 이용해서 1부터 범위까지의 숫자마다 d(n)을 실행할 수 있도록 했다. 그 결과를 noSelfNumber 이라는 배열에 넣은 뒤에 이를 1 ~ 범위(10000) 까지의 수를 가지고 있는 배열과 비교했다.

둘을 비교했을 때 해당 수가 noSelfNumber 의 배열에 없는 수라면 셀프넘버 이기 때문에 출력할 수 있도록 했다.

결과는 예상했던 것처럼 잘 나오긴 했다. 나오긴 했는데...😮‍💨 연산 시간을 전혀 고려하지 않은 무식한 방법이었다. 위의 경우를 생각해보면 1부터 10000까지의 숫자에 모두 d(n)을 사용하게 되고 각 d(n)의 경우도 범위까지 계속해서 재호출되기 때문에 엄청난 시간이 걸린다. 그래서 역시나 백준에서도 시간 초과가 나왔다.

몇번의 시도 끝에 도달한 결론은, 재귀함수를 굳이 사용할 필요가 없었다는 점이다. 재귀함수를 사용하며 1 ~ 범위까지의 숫자를 반복시킬 경우에 의미 없는 중복이 계속 발생한다. 1부터 시작한 수열(1, 2, 4, 8, 16 ...) 의 경우를 보면 2에서 시작한 수열( 2, 4, 8, 16 ...) 이나 4에서 시작한 수열 (4, 8, 16, ...) 의 경우와 계속 중복되고 있음을 알 수 있다. 한마디로 이렇게 코드를 짜면 욕먹는다.🥵

// 다시 작성한 코드
// 재귀를 없애고 한번만 실행되는 d(n) 함수를 선언
function d(n) {
  let N = String(n);
  let result = Number(n);
  for (let i = 0; i < N.length; i++) {
    result += Number(N[i]);
  }
  return result;
}

// d(n)의 결과는 셀프넘버가 아니므로 false를 넣음.
function solution(range) {
  let selfNumber = [...Array(range)].map(() => true);
  for (let i = 1; i < range; i++) {
    selfNumber[d(i)] = false;
    if (selfNumber[i]) {
      console.log(i); // true인 index 출력
    }
  }
}

solution(10000);

위의 코드는 다시 작성해 제출했던 코드이다. 맨 처음 코드보다 빠른 연산 속도를 보인다.

함수 d(n) 을 선언하면서 재귀함수를 제거했다. 어차피 1부터 범위까지 d(n)을 실행할 예정이기 때문에 재귀함수를 통해서 불필요한 중복 요소를 만들 필요가 없었다.

solution() 의 경우에는 selfNumber 배열을 만들고 안의 값을 모두 true로 넣어주었다. 그 이후에 d(n) 함수를 반복문을 통해서 호출하면서 나오는 결과값의 index에 false를 넣어서 셀프넘버가 아닌 숫자들을 구별할 수 있도록 했다.

마지막으로 true 값을 가지고 있는 index를 출력하면 원하는 결과값을 얻을 수 있다.

이번 문제를 풀면서 시간복잡도에 대해서 생각해보게 됐다. 위의 두 코드의 경우 시간 차이가 확연히 느껴질 정도로 나는 것을 보면서 큰 충격을 받았다. 만약 처음의 코드가 들어간 서비스를 내놓았다면 어떻게 됐을까. 아마 사용자들의 부정적인 피드백이 쏟아졌을 것이다. 단순히 기능이 돌아가는 것이 중요한게 아니라 효율적이고 메모리 낭비가 없는지에 대해서 더욱 고민하며 코드를 작성해야겠다.