문제
셀프 넘버는 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보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다.
이 문제를 보고 파이썬 자료형 중 set을 사용하면 되겠다고 생각했습니다. 하지만 set은 개인적으로 저에게 안 익숙한 자료형이라서 결국 다른 분들의 힌트를 통해 문제를 해결할 수 있었습니다. 코드에서 numbers는 1부터 10000까지의 자연수이고, not_self d함수로 얻어진 수를 의미합니다.
def d_func(n):
m = 0
if n < 10:
m = n + n
elif n < 100:
m = n + n//10 + n%10
elif n < 1000:
m = n + n//100 + (n%100)//10 + n%10
else:
m = n + n//1000 + (n%1000)//100 + (n%100)//10 + n%10
if m <= 10000:
not_self.add(m)
d_func(m)
return not_self
numbers = set()
not_self = set()
for i in range(1,10000):
numbers.add(i)
not_self.union(d_func(i))
self_number = sorted(numbers - not_self)
for i in self_number:
print(i)
set자료형은 수학의 집합 연산처럼 사용할 수 있습니다. 그래서 1부터 10000까지의 자연수에서 d함수의 결괏값을 차집합 연산을 했고, 셀프 넘버를 구할 수 있었습니다. 그러나 각 자릿수를 더하는 함수를 만들 때, if문을 사용했는데 코드가 보기에도 힘들고 길어졌습니다. 그래서 아래와 같이 조금 더 파이썬스럽게 코드를 바꿔봤습니다.
def d_func(n):
m = n
n = str(n)
for i in n:
m += int(i)
if m <= 10000:
not_self.add(m)
d_func(m)
return not_self
numbers = set()
not_self = set()
for i in range(1,10001):
numbers.add(i)
not_self.union(d_func(i))
self_number = sorted(numbers - not_self)
for i in self_number:
print(i)
if 대신 반복문으로 문자열을 처리했습니다. 이전 코드보다는 간결해졌습니다. 하지만 1부터 10000까지 d_func를 재귀시켰을 때 꽤 많은 시간이 걸릴 것이라고 생각됩니다. 이 상황의 해답은 다른 분의 코드를 참고해서 찾을 수 있었습니다.
numbers = set()
not_self = set()
for i in range(1,10001):
numbers.add(i)
for j in str(i):
i += int(j)
not_self.add(i)
self_number = sorted(numbers - not_self)
for i in self_number:
print(i)
그냥 재귀 함수를 사용하지 않고 반복문에서 바로 d연산을 하는 것으로 해결할 수 있었습니다. 이렇게 해서 얻은 결과는 이전의 코드보다 월등하게 빨랐습니다. (코드의 길이도 짧고 기간도 적게 걸리고... 제가 생각한 것보다 훨씬 좋은 코드입니다 ㅠㅠ)
제가 최종 코드를 완성하기 위해 참고한 글을 아래 링크에 첨부합니다.
https://wook-2124.tistory.com/252
'개발 > 알고리즘' 카테고리의 다른 글
[BOJ(백준) 1065]한수 - 파이썬 풀이 (0) | 2021.05.28 |
---|---|
[BOJ(백준) 5622] 다이얼 - 파이썬의 switch와 딕셔너리 (0) | 2021.05.28 |
[BOJ(백준) 4344] 평균은 넘겠지 - 파이썬 풀이 (0) | 2021.05.23 |
[BOJ(백준) 10951] A+B - 4, 파이썬 문자열의 EOF (0) | 2021.05.23 |
[BOJ(백준) 1110] 더하기 사이클 - 파이썬 풀이 (0) | 2021.05.22 |