BOJ 4673번: 셀프 넘버

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

4673번: 셀프 넘버

처음에는 정말 단순하게 이중 for문을 사용해서 생성자가 있는지 없는지 체크하는 방식으로 아래와 같이 코드를 작성했다.

for i in range(1, 10001):
    flag = True
    for j in range(1, i):
        num = j
        for k in str(j):
            num += int(k)
        if (num == i):
            flag = False
            break
    if (flag == True): print(i)

위 코드는 python으로 제출하면 시간초과가 났고, pypy3로 제출하니 통과가 되었다. 하지만 다른 분들의 풀이를 보니... 내가 너무 시간복잡도를 생각하지 않고 무식하게 풀었다는 생각이 들었다. 저렇게 풀어버리면 불필요한 반복된 연산이 너무 많아진다. 뇌가 너무 멍청해진 것 같다.

 

그래서 다시 푼 방법은 먼저 1부터 10000까지 수로 만들 수 있는 d(n)을 쫙 계산한 후에 거기에 없는 숫자만 출력을 하는 방법이다.

nums = [x for x in range(1, 10001)]

for i in range(1, 10001):
    dn = i
    for j in str(i):
        dn += int(j)
    if (dn in nums):
        nums.remove(dn)
    
for i in nums:
    print(i)

처음 제출한 코드 삭제하고 싶다 너무 멍청해!