[백준/4673/파이썬3(python3)] 셀프 넘버

문제

셀프 넘버는 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 42 53 64 | | <-- a lot more numbers | 9903 9914 9925 9927 9938 9949 9960 9971 9982 9993

풀이

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)

설명

코드의 흐름은 단순하다. 일단 1부터 10,000까지의 자연수 수열을 set형태로 만든다. set자료형으로 자연수 set을 만든 이유는 이 문제를 푸는 전략을 다음과 같이 설정했기 때문이다.

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

파이썬에서 set은 중학교 과정에서 배우는 집합(요즘은 모르겠는데 난 중1때 배웠다)의 개념이라고 보면 되는데 set끼리 빼면 각 set의 차집합이 결과값으로 남는다. 위의 코드에서 self_number_set이라는 변수가 해당 차집합이 들어있는 변수라고 생각하면 된다.

 전략은 이렇고, 이제는 생성자가 있는 숫자를 구하는 로직을 살펴보자. 생성자가 있는 숫자는 다음과 같다고 한다.

양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다.

여기에서 말하는 d()가 생성자가 있는 숫자를 만드는 함수이다. 문제에서 힌트로 주어진 것은 어떠한 숫자가 셀프넘버인지 아닌지 구하는 방법이 아닌, 생성자가 있는 숫자를 만드는 방법이다. 그렇기 때문에 1부터 10,000까지에 있는 숫자 중 생성자가 있는 숫자를 전부 구한 뒤에 자연수에서 빼는 방법이 타당할 것이다. 문제 속에 답이 있다는 말처럼, 문제에서 주어진 힌트로 푸는 것이다.

생성자가 있는 숫자를 구하는 방법은 위에 써진 것과 같다. 주어진 수가 있으면 해당 자릿수를 앞자리 수에서부터 각 숫자로 다시 빼내어 각각을 더한다. 말 그대로 위의 인용문에 써있는 공식이다. 그렇게 해서 모든 1부터 10,000까지의 숫자에 대한 생성자가 있는 숫자set(generated_number_set)이 만들어진다. 하지만 10,000까지 모든 자연수를 검사하므로 10,000이 넘어가는 ganerated_number가 생성된다는 점을 알아두자.

 위의 과정은 아래 코드를 직접 실행해보면 더욱 쉽게 파악할 수 있을 것이다.

natural_number_set = set(range(1, 1001))
generated_number_set = set()

for i in range(1, 1001):
    print('currnet i = ' + str(i))
    for j in str(i):
        print('currnet j = ' + str(j))
        i += int(j)
    print('**managed num = ' + str(i))
    generated_number_set.add(i)
    print()

print(generated_number_set)
print(natural_number_set)

self_numbers_set = natural_number_set - generated_number_set
print(sorted(self_numbers_set))

너무 많은 숫자가 출력되기 때문에 범위를 10,000까지에서 1,000로 줄였다. 해당 코드를 실행해보면 어떻게 ganerated_number가 생성되고 어떻게 집합이 구성되고 결과값은 또 어떻게 남는지 명확하게 알 수 있을 것이다.