백준 - 4673 (Python) - 셀프 넘버

박준영·2021년 6월 29일
0
post-thumbnail

셀프 넘버


문제

셀프 넘버는 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. 1부터 10,000까지의 자연수 set을 만든다.
  2. 1부터 10,000사이에 존재하는, 문제에서 말하는 "생성자"가 있는 숫자(각 자릿수 단위를 1의 단위로 치환하여 원래의 숫자에 다시 더해 나온 숫자)를 모두 구하여 새로운 set에 넣는다.
  3. 1에서 만든 자연수 set에서 2에서 만든 생성자가 있는 set을 뺀다.
  4. 그러면 생성자가 없는, 문제에서 말하는 "셀프 넘버"만이 남는다.
  • 풀이

num_set = set(range(1, 10001)) # 1부터 10,000까지의 자연수 수열
generated_num_set= set() # 생성자 수열

for i in range(1, 10001):
    for j in str(i): # i 값을 문자열로 변환하여 각 자리수의 숫자를 분리시킨다. 
    	# ex) i가 21일 경우 ('2','1')
        i += int(j) # 분리시킨 수들을 각자 정수로 변환하여 원래의 수에 더해준다.
        # ex) 21 + 2 = 23 -> 23 + 1 = 24
    generated_num_set.add(i) # 그렇게 나온 생성자들을 수열에 추가한다.

self_number = num_set - generated_num_set 
# 수열끼리 빼주면 차집합이 나오게 된다. 그러므로 생성자가 없는 수인 셀프 넘버들만 남게 되는 것.

for i in sorted(self_number): # 수들을 오름차순으로 정렬한 뒤 출력
    print(i)

0개의 댓글