문제
문제 해설
하나의 노드로 부터 부모를 타고 올라가 루트까지 도달하는 문제입니다.
union-find의 find와 parents 개념을 사용하면 쉽게 접근할 수 있습니다.
다만, 여기서 중요한 점은 1 <= enroll <= 10,000, 1<= seller <= 100,000이기 때문에 union-find의 개념을 사용해도 시간 초과가 발생하는 문제가 생깁니다.
이 문제는 트리 구조를 띄고 있고, 특성상 최악의 경우 한 줄기를 가지는 트리의 형태가 나올 수 있습니다.
그럼 enroll이 10,000 seller가 100,000인 경우를 가정한다면, 한 줄기를 가지고 깊이가 10,000인 트리를 100,000번 탐색해야하는 최악의 경우가 탄생하므로 시간 초과가 납니다.
-
단, 10% 를 계산할 때에는 원 단위에서 절사하며, 10%를 계산한 금액이 1 원 미만인 경우에는 이득을 분배하지 않고 자신이 모두 가집니다. -
1 <= amount <= 100
이 두 개의 제한 사항을 이용하면 시간 초과를 피할 수 있습니다. 최대로 벌 수 있는 돈은 10,000으로 한정되어 있고, 원 단위에서 절사하기 때문에 줄 수 있는 돈이 없다면 그 자리에서 재귀를 종료하는 방식으로 코드를 짠다면 최대 깊이가 5인 재귀 형태를 띄고 시간 복잡도가 훨씬 줄어들게 됩니다.
풀이 코드
def find(parents, money, number, answer):
# 민호까지 돈이 들어오거나 줄 돈이 없으면 종료
if parents[number] == number or money // 10 == 0:
answer[number] += money
return
send = money // 10
mine = money - send
answer[number] += mine
find(parents, send, parents[number], answer)
return
def solution(enroll, referral, seller, amount):
n = len(enroll) # 총 사람 수(민호 포함 X)
answer = [0] * (n + 1) # 민호 포함
d = {} # 이름-번호의 key-value를 가지는 딕셔너리
parents = [i for i in range(n + 1)] # 각자 자신을 부모로 초기화
# 이름-번호로 딕셔너리에 저장
for i in range(n):
d[enroll[i]] = i + 1
# 추천인 입력
for i in range(n):
if referral[i] == "-": # 민호가 추천인
parents[i + 1] = 0
else:
parents[i + 1] = d[referral[i]]
# 칫솔 정산
for i in range(len(seller)):
find(parents, amount[i] * 100, d[seller[i]], answer)
return answer[1:]