[JavaScript ] BeakJoon 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보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다.

예제입력

없음

 

예제 출력

1
3
5
7
9
20
31
42
53
64
 |
 |       <-- a lot more numbers
 |
9903
9914
9925
9927
9938
9949
9960
9971
9982
9993

 

---

 

문제풀이

const iter = 10000; //문제에서 10000으로 범위 제한
solution();

function solution() {
  //모든값을 true로 초기화
  let numArray = Array.from({ length: 10000 }, () => true);

  //셀프 넘버가 있는지 체크하기
  for (let i = 1; i < iter; i++) {
    if (numArray[i] != false) selfNumCheck(i + 1); // 이미 체크한 값은 중복으로 처리 안하기

    numArray[selfNumCheck(i) - 1] = false; //10000 이하의 생성자는 모두 false로 처리
  }

  //결과 출력
  for (let i = 0; i < iter; i++) {
    if (numArray[i]) console.log(i + 1);
  }
}

function selfNumCheck(num) {
  let temp = num;
  let size = (temp + '').length; //넘어온 숫자의 자릿수 ex) 7 = 한자릿수, 18 = 두자릿수, 182 = 세자릿수
  let result = num;

  for (let i = 0; i < size; i++) {
    result += +(temp + '')[i];
  }
  //재귀 함수로 구현, iter값 까지 모든 생성자를 찾음
  if (result < iter) selfNumCheck(result);

  return result;
}

 

설명

문제를 보면 ' n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다.' 이 부분을 보고 재귀함수를 사용해야 한다고 생각이 들었다.

재귀 함수를 사용하기위해 숫자를 더하는 과정을 함수로 처리하였다.

 Array의 from 함수를 통해 반복문을 사용하지 않고 배열의 length를 설정하고 모든값을 true로 초기화 하였다.

number 를 파라미터로 넘긴 후, 1자리 수 2자리 수 3자리수 등 몇번을 더해야하는지 구별하기 위해 넘어온 값을 +""을 통해 string 으로 묵시적 형변환 시킨 후  생성자의 값을 구했다.

함수를 호출하는 과정을 1~10000을 반복해서 진행해도 결과에 문제는 없지만, 쓸데없는 연산을 매우 많이 처리한다.

그래서, 재귀함수를 통해 이미 값을 체크한 값들은 다시 체크하지않기 위해 조건문을 하나 추가했다.

또한 생성자를 생성하며 방문한 배열은 false로 처리하여 

결과적으로 ture값을 유지한 값은 생성자가 없는 self number임을 알 수 있다.

 

 

---

출처

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

4673번: 셀프 넘버