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

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]