백준 4673번 셀프 넘버 파이썬 풀이

BOJ 4673문제

def d(n) :     # d(n)함수
    sum = n
    while n != 0 :
        sum += n % 10
        n //= 10
    return sum

def findSelfNumber(num) :   # 생성자 유무 확인
    array = []
    for i in range(1, num) :
        array.append(d(i))
    for i in array :
        if num == i :
            return 1
    return 0

for i in range(1, 10001) :    
    if findSelfNumber(i) == 0 :
        print(i)

내가 작성한  파이썬 코드이다. 정답은 잘 출력되는데 시간초과가 나서 잘못된 방법으로하고 있다는걸 알게되었고 반복문 안에서 반복문을 호출하는 함수를 사용하게 되면서 그런걸로 예상되었다.

반복문이 O(n)의 시간 복잡도를 갖게 되는데 반복문 안에서 반복문을 호출하게 되면 O(n^2)가 되는 부분을 해결해 볼까 하는게 제일 먼저 떠올랐다.

def d(n) :
    sum = n
    while n > 0 :
        sum += n % 10
        n //= 10
    return sum

generated_numbers = set()
for i in range(1, 10001):
    generated_numbers.add(d(i))

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

 

같은 코드지만 아래는 시간초과되던 문제를 해결했다. set이라는 방법을 알게되고 다시 내 코드를 수정했다.

 

 

처음 썼던 코드는 왜 애초에 findSelfNumber 함수로 뺐는지도 모를 정도로 생각없이 코드를 짰었나 싶었다. 오랜만에 알고리즘 풀이를 다시 시작했는데 집중도 잘 안되고 낯설어서 푸는데 오래 걸렸다. 다음 문제는 조금 더 빠르지만 신중하게 풀었으면 좋겠다.