문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/77486
이 문제의 enroll의 길이가 1만개가 전부라 단순하게 재귀함수를 호출하면 O(N^2) 졍도로 시간복잡도가 나오지 않을까? 라는 생각에 재귀함수 호출로 문제를 풀이하려고 시도했다.
def to_parents(parents, moneys, name, earn_money):
if parents[name] == "":
moneys[name] += earn_money
return
else:
moneys[name] += earn_money - earn_money // 10
to_parents(parents, moneys, parents[name], earn_money // 10)
def solution(enroll, referral, seller, amount):
money = {'-':0}
parent = {'-': ""}
for index, name in enumerate(enroll):
money[name] = 0
parent[name] = referral[index]
for index, name in enumerate(seller):
earn = amount[index] * 100
to_parents(parent, money, name, earn)
answer = []
for name in enroll:
answer.append(money[name])
return answer
(처음에는 ceil과 round를 사용했는데, 정확히 문제에 제시된 입출력 예시 2가지와 test 1만 통과한 뒤로 모두 틀렸다. 그래서 단순하게 고침)
결과는 이런식으로 나왔다. 그래서 뭐가 문제인지 검색하다가.
파이썬의 기본 재귀 제한
기본 재귀 제한이 1000으로 설정되어 있어서, 이를 초과하면 RecursionError가 발생합니다.
을 발견했다. 흠.. 그러면 제한을 풀어주면? 시간초과가 나왔다. ㅠㅠ 밑의 코드를 추가해주면 되긴한다..
더보기
import sys
# 재귀 깊이 제한을 10000으로 설정
sys.setrecursionlimit(10000)
def to_parents(parents, moneys, name, earn_money):
current = name
while current != "":
earn_for_parent = earn_money // 10
moneys[current] += earn_money - earn_for_parent
earn_money = earn_for_parent
current = parents[current]
if earn_money == 0:
break
def solution(enroll, referral, seller, amount):
money = {name: 0 for name in enroll}
money["-"] = 0
parent = {enroll[i]: referral[i] for i in range(len(enroll))}
parent["-"] = ""
for i in range(len(seller)):
earn = amount[i] * 100
to_parents(parent, money, seller[i], earn)
return [money[name] for name in enroll]
결국 위처럼 코드를 재귀함수에서 반복으로 고쳐서 다시 풀어서 맞았다.
오늘의 결론
1. 파이썬의 기본 재귀 제한은 1000번이다.
2. ceil이나 round를 먼저 떠올리기 전에 단순 식으로 해결 할 수 있는 방법을 찾아본다.
'TIL > 에러 해결 모음' 카테고리의 다른 글
[Typescript] 맥 command not found: tsc 해결 방법 (0) | 2024.05.30 |
---|