백준 4673. 셀프 넘버

문제 설명

양의 정수 n 에 대해서 n과 n의 각 자리 수를 더하는 함수 d(n)

n, d(n), d( d(n) ) ... 과 같이 무한 수열 생성 가능

n은 d(n)의 생성자

생성자가 한 개보다 많은 경우도 존재 → 101의 생성자는 91, 100

생성자가 없는 숫자는 셀프 넘버

 

10,000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

 

입력

X

 

출력

10,000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다.

 

시간 초과된 코드

# 1. 처음 풀이, 시간 초과
def constructor(n):
    for num in range(1, n):
        sum = num
        while num > 0:
            x = num % 10
            sum += x
            num //= 10
        if sum == n:
            return True
    return False

for i in range(1,10000 + 1):
    if constructor(i) == False:
        print(i)

# 2. 처음 풀이와 접근법은 같지만 str 함수를 활용한 풀이
def constructor(n):
    for i in range(1, n):
        st = str(i)    
        total = sum(list(map(int, st))) + i
        if total == n:
            return True
    return False

for i in range(1,10000 + 1):
    if constructor(i) == False:
        print(i)

 

위 코드는 1~10000까지의 숫자를 하나씩 데리고 와서,

해당 숫자까지의 숫자들을 더해보면서 생성자의 유무를 확인한다.

 

있으면 true, 없으면 false를 출력하는데,

n 이 커질수록 n^2와 비슷한 시간 복잡도를 갖게 된다.

 

 

---

 

 

[시간복잡도 계산]

보통 n으로 구성된 O()를 계산했을 때의 값이 1억 정도면 1초 정도의 시간이 걸린다.

정확한 값은 아니고 문제의 알고리즘에 따라서 달라질 수 있다.

 

위의 시간 복잡도 계산법을 적용할 때,

해당 문제는 10000 까지의 수를 다루기 때문에 위의 코드로 실행을 시킬 경우

시간 초과가 발생할 수 있다.

 

 

---

 

 

 

코드

numbers = set(range(1, 10001))
generated_num = set()

for i in range(1, 10001):
    for j in str(i): # 많아 봤자 해당 숫자의 자리수만큼을 더 돈다
        i += int(j)
    generated_num.add(i)

self_num = sorted(numbers - generated_num)
for num in self_num:
    print(num)

 

1부터 10000까지의 숫자 집합을 만들고

생성자가 존재하는 숫자 집합을 만들어서

두 집합의 차집합을 구하는 형태로 셀프 넘버 집합을 만드는 방법으로 접근한다.

 

위 방법은 각 숫자마다 많아봤자 해당 숫자의 자리수만큼만을 더 돌기 때문에

O(N)만큼의 시간 복잡도로 문제를 해결할 수 있다.

 

집합 자료형은 순서가 없기 때문에 sorted() 함수를 통해서 정렬을 해주고

반복문으로 각 줄마다 정렬된 숫자를 출력해주면 된다.