[백준/파이썬3/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
	.......
	9949
	9960
	9971
	9982
	9993

풀이

def d(n):  
    result = n
    while n != 0:
        result += n%10
        n //= 10
    return result
 
list1 = []
 
for i in list(range(1,10001)):
  list1.append(d(i))
for j in range(1,10001):
  if j not in list1:
    print(j)

위와 같이 처음에는 배열에 셀프넘버를 넣고 1부터 10000까지 순차적으로 하나씩 배열에 있는지 검사하려 하였지만 아래와 같이 넣는 동시에 검사를 하여도 문제가 없다. (샐프넘버가 생성될때 들어가는 i의 값이 샐프넘버보다 항상 작기때문에.)

 

 

def d(n):  
    result = n
    while n != 0:
        result += n%10
        n //= 10
    return result
 
list1 = []
 
for i in list(range(1,10001)):
  list1.append(d(i))
  if i not in list1:
    print(i)

n이 주어지면 result라는 변수에 n을 10으로 나눈 나머지를 계속해서 더하고 10으로 나눠준다. 그래서 n이 0이 될때까지 반복.

준비가 되었다면 이제 배열 (list1) 하나를 만들어준다. 그리고 1부터 10000까지 반복할 for문을 사용하여 배열 내부에 비는 숫자열을 하나씩 검사해서 출력하면된다.

 

(이해를 돕기 위해서, list1이라는 배열 내부에는 아래 테이블 처럼 값이 채워진다.)

 

 

 

 

추가풀이

문제 풀이후 검색 결과 더 괜찮은 방법을 찾아내었다.

위의 방법(68ms)이 set을 사용, 아래방법(656ms)이 일반 배열을 사용

또한 set()이라는 함수는 몰랐는데 차 집합 교집합 공집합 등 아주 유용하게 사용 가능 할듯.

아래 코드 소스 원래 주소 링크 => 디스프로그래머님 블로그

natural_number_set = set(range(1, 10001))
generated_number_set= set()
 
for i in range(1, 10001):
    for j in str(i):
        i += int(j)
    generated_number_set.add(i)
 
self_number_set = natural_number_set - generated_number_set
 
for i in sorted(self_number_set):
    print(i)