[Programmers]다단계 칫솔 판매(Python)/Tree

[Programmers]다단계 칫솔 판매(Python)/Tree

728x90

https://programmers.co.kr/learn/courses/30/lessons/77486

새로 가입한 알고리즘 스터디에서 풀었던 문제

문자열을 이용한 저장을 구현할 때 딕셔너리를 사용하는게 많이 편해졌다

이 문제도 풀다풀다 코드가 엄청 길어졌지만 최종적으로는 엄청나게 짧아진 문제

이런 식으로 각 child는 모든 anscestor에게 수익을 분배하게 되는데, 각 노드가 얻게 되는 수익의 총합을 구하는 문제였다

트리를 제대로 이해하고 있으면 풀 수 있을 것 같다 !! 나는 트리 문제를 오랜만에 풀어서 그런지 조금 헷갈렷다ㅠ

def solution(enroll, referral, seller, amount): salary=dict() parent=dict() salary['-']=0 for i in range(len(enroll)): salary[enroll[i]]=0 parent[enroll[i]]=referral[i] for i in range(len(seller)): s=seller[i] p=amount[i]*100 while s!='-': salary[s]+=p-(p//10) p=p//10 if p==0:break s=parent[s] return [salary[e] for e in enroll]

from http://2jinishappy.tistory.com/306 by ccl(A) rewrite - 2021-09-12 02:00:21