백준 4673 파이썬 - 생성자가 아닌 셀프 넘버 출력하기!

백준 4673번 - 셀프 넘버 with Python

 

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

 

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

4673번: 셀프 넘버

---

먼저, 셀프 넘버를 구하기 위해선 생성자를 구해야한다.

셀프넘버만을 독단적으로 구하기는 어렵기 때문에 자연수에서 생성자 목록을 빼서 셀프넘버를 구해야 하기 때문이다.

 

숫자를 각 단위 별로 쪼개는 데에는 쉽게 두 가지 방법이 있다.

1. 숫자를 10, 100, 1000, ...으로 나눈 나머지를 활용하는 방법

2. 숫자를 string으로 바꾼 다음 문자열의 각 자리수에 있는 문자를 추출하는 방법

이 있다.

 

이 문제에는 두 번째 방법을 사용하는 것이 더 적절하므로 두 번째 방법을 사용하도록 하겠다.

for문을 이용하여 각 자리수를 추출해낸 후 더해주면 되겠다.

 

먼저, 생성자의 수를 구한 것을 어딘가에 저장을 해야하는데, set함수를 이용해 저장해주겠다.

set은 집합이라는 뜻인데, 중복을 제거해서 보관해준다는 특징이 있다. set을 이용해주는 이유는 생성자가 2개 이상인 경우도 있기 때문이다.

 

nature_num = set(range(1,10001))
numList = set()

for i in nature_num:
    for j in str(i):
        i += int(j)
    numList.add(i)

1~10000개의 자연수목록에서 생성자 목록에 포함된 수를 제거해야하므로,

자연수 목록(nature_num)과 생성자 목록(numList)을 만든다. 두 목록의 타입은 집합(set)으로 하겠다.

작은 for문을 통해 생성자를 만들어 주는 식을 만들었고,

큰 for문을 통해 이 생성자를 만드는 과정을 총 자연수목록만큼 반복하도록 하였다.

 

self_num = sorted(nature_num - numList)
    
for i in self_num:
    print(i)

그리고 자연수 목록에서 생성자 목록을 빼서 셀프넘버 목록(self_num)을 만들었고,

이를 오름차순으로 정렬해야하므로 sorted()를 이용하여 정렬해주었다.

 

이 셀프넘버 목록에서 각 숫자들을 print해주어야하므로, 역시 for문을 사용하여 print를 할 수 있게 코드를 작성하였다.

 

최종코드는 다음과 같다.

nature_num = set(range(1,10001))
numList = set()

for i in nature_num:
    for j in str(i):
        i += int(j)
    numList.add(i)
    
self_num = sorted(nature_num - numList)
    
for i in self_num:
    print(i)