[4673] 셀프 넘버 - Python

문제

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

 

내 코드

nonSelfNum=[]

def findNonSelfNum(r):
    for n in range(1,r+1):
        res = n
        while n >= 1:
            res += int(n%10)
            n = int(n/10)
        nonSelfNum.append(res)

findNonSelfNum(10000)
for n in range(1,10001):
    if n not in nonSelfNum:
        print(n)

 

과정

문제를 처음 보고 생각해낸 풀이 방법은 두가지였다.

 

1) 1부터 시작해서 d(n)이 10000보다 클 때까지 계산. 셀프 넘버가 아닌 리스트 만든 후 제외하고 출력.
2) [1-10000] 리스트 하나하나를 셀프 넘버인지 검사. 셀프 넘버인 경우 출력.

 

2번 풀이의 경우 셀프 넘버인지 계산하는 함수를 작성해서 매번 함수를 호출해야 하는데, 함수의 로직은 1번과 동일하지만 함수 호출 횟수가 압도적으로 많고 중복된 계산이 발생하기 때문에 1번 방법을 선택했다.

 

findNonSelfNum 함수를 작성하는 것은 어렵지 않았다. 프로그램의 확장성을 위해 최대 숫자를 함수에 인자로 전달하고, 주어진 범위 내에서 d(n)을 계산해 nonSelfNum 리스트에 추가하는 과정을 반복했다. % 연산자를 이용해 각 자릿수를 반복문으로 더하면 끝.

 

그러나 생각보다 시간을 더 써야 했는데, 문제는 두가지였다. 

 

1) n<=d(n) 이라는 결론을 내고 문제를 풀었는데, 중점을 n이 아닌 d(n)에 맞춘 것.

모든 셀프 넘버가 아닌 수를 계산하는 함수를 작성했던 이유는 n<=d(n)이기 때문이었다. d(n)은 무조건 생성자(n)보다 크기 때문에 원하는 상한값 이하의 숫자를 모두 계산하면 그 안의 셀프 넘버를 모두 찾을 수 있다. n이 아니라 d(n)을 상한값으로 설정했던 것이 문제였다. 처음 작성한 코드에서 r=100으로 놓고 테스트를 해봤더니 셀프 넘버가 아닌 99가 함께 출력되는 문제가 있었다. 초기 코드에는 while문 아래에

if int(res) > r:
	break

라는 코드가 있었다. r을 넘는 nonSelfNum이 하나 나오는 순간 계산을 종료하는 코드인데, d(87)=102이기 때문에 n=87에서 반복문을 탈출해 버린 것(99의 생성자는 90이다). 여러 번의 프린트 디버깅(ㅋㅋ) 결과 r보다 작은 모든 n을 검사해야 한다는 것을 깨닫고 해당 코드를 삭제했다.

 

2) 나눗셈 연산을 하며 자료형을 신경쓰지 않은 것.

나눗셈 연산을 하면 소수점 아래 숫자는 버려지는 것에 익숙해져 있었다. C의 폐해.. 파이썬은 숫자의 자료형이 고정되어있지 않기 때문에 연산을 반복하다 보면 소수점 아래 숫자가 더해지며 정수 범위로 넘어오는 문제가 생겼다. 이 문제는 형 변환을 이용해 쉽게 해결했다.

 

...

코딩을 오랜만에 했더니 머리가 굳은게 느껴진다.. 열심히 해야지