[백준 4673] 셀프 넘버 (Node.js)

문제 링크

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

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, 37, 51, 57, 69, 84, 96, ... 

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보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

 

---

답안 (map 을 이용한 풀이)

function d(n) {
    let result = n
    let left = 0
    while (n) {
        left += n % 10
        n = Math.floor(n / 10)
    }
    return result + left
}

function solution(number) {
    const map = new Map(new Array(10000).fill(0).map((_, i) => [i + 1, true]))
    let answer = ""
    for (let i = 1; i <= number; i++) {
        map.delete(d(i))
    }
    for (const key of map.keys()) {
        answer += key + "\n"
    }
    return answer
}

console.log(solution(10000))

• 1부터 10000까지의 숫자 중 셀프넘버를 출력하는 문제이다.
• 즉, 1부터 10000까지 나열된 수열에서 생성자가 있는 수를 빼면 셀프넘버만 남길 수 있다.
• 이를 위해 생성자를 만드는 함수인 d(n)을 헬퍼 함수로 만든다. 
• 함수는 생성수를 만드는 공식을 로직화해서 만든다. 각 자릿수를 더하는 것이니 10을 모듈로(%) 연산하여 나머지 값에 더하고, 계속 10으로 나눠주어 자릿수를 잘라내고 while의 종료조건에 부합되도록 만든다.  
• (만약 헬퍼 함수에 n으로 987이 전달되면 987 + 9 + 8 + 7이 되어 1011이 될 것이다.)
• 최종적으로 문제를 푸는 solution 함수를 만든다.
• 이 때, 충분히 배열로도 풀 수 있지만, 수열 내에서 계산된 뒤 리턴되는 수를 빼는 것이므로, map 자료형을 쓰는 것이 시간복잡도상 이롭다.