블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.본 글은 [ 백준 ] 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부터 10,000까지의 수를 키로 갖고 값으로 카운트 횟수를 가지는 딕셔너리 변수를 하나 만든 다음 10,000까지 반복문을 돌면서 생성된 숫자를 통해 해당 딕셔너리 변수에 키로 접근하여 값을 하나씩 증가시킨다. 그리고 다시 10,000까지 반복문을 돌면서 값이 0인 경우가 곧 셀프 넘버가 된다.
이때 생성된 숫자는 내장함수 sum() 및 리스트 컴프리헨션을 사용하여 숫자를 문자열로 만든 다음 정수형으로 바꾸어 리스트의 요솔 추가해서 그 합산을 구하면 된다.
이렇게 풀 경우 생성자가 2개인 수만 따로 구할 수도 있는 등 조금 더 확장된 문제 풀이가 가능하다.
나의 풀이
접근법을 토대로 문제를 풀면 아래와 같다.
nums: dict[int, int] = { num + 1: 0 for num in range(10000) }
for num in range(10000):
constructed_num: int = (num + 1) + sum([ int(n) for n in str(num + 1) ])
if constructed_num <= 10000:
nums[constructed_num] += 1
for num, count in nums.items():
if not count:
print(num)Big-O
10,000까지 돌기 때문에 시간 복잡도는 O(10,000)이 된다. 내부에서 내장함수 sum() 및 리스트 컴프리헨션을 사용하는 경우도 결국 내부적으로 반복문이 도는 것이지만 최악의 경우에도 숫자 10,000이기 때문에 다섯 자리라서 O(5) 밖에 소요되지 않는다. 따라서 O(10,000), 더 나아가 어떤 특정 숫자 N까지 출력하는 경우 O(N)이 된다.
