반응형
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 함수로 뺐는지도 모를 정도로 생각없이 코드를 짰었나 싶었다. 오랜만에 알고리즘 풀이를 다시 시작했는데 집중도 잘 안되고 낯설어서 푸는데 오래 걸렸다. 다음 문제는 조금 더 빠르지만 신중하게 풀었으면 좋겠다.
반응형
'알고리즘' 카테고리의 다른 글
백준 9012 괄호 파이썬 풀이 (2) | 2024.01.15 |
---|---|
백준 25206 너의 평점은 파이썬 풀이 (2) | 2024.01.14 |
백준 2839 설탕 배달 파이썬 풀이 (2) | 2024.01.12 |
백준 2556번 별 찍기 - 14 파이썬 풀이 (0) | 2024.01.12 |
백준 2440번 별 찍기 - 3 파이썬 풀이 (0) | 2024.01.12 |