[백준] 셀프 넘버 (Python)

✏️ 문제

4673번: 셀프 넘버

✏️ 풀이

- 1차시도

1부터 10001 까지에 대해 해당 자연수가 1부터 10000까지의 자연수 중 하나를 생성자로 가지는 지 판별하였다.

결과 : 시간 초과(O(n^2))

for num in range(1,10001):
    for i in range(1,10000):
        if i > num:
            continue
        if num == i + sum(list(map(int, list(str(i))))):
            break
    else:
        print(num)

- 성공

1부터 10000까지의 자연수를 생성자로 가지는 셀프넘버를 미리 모두 구하여 배열에 저장한다.

그 후, 1부터 10001까지에 대해 셀프넘버 배열에 속하지 않는 것들을 출력한다.

시간복잡도가 O(n)으로 줄어든다.

✏️ 코드

d = []
for i in range(1,10000):
    d.append(i + sum(list(map(int, list(str(i))))))

for i in range(1,10001):
    if i not in d:
        print(i)