프로그래머스 다단계칫솔판매 (Python)

코딩테스트 연습 - 다단계 칫솔 판매 | 프로그래머스 (programmers.co.kr)

문제에 대한 설명은 링크를 직접 들어가서 확인하는것이 가장 좋을것이라고 생각된다.

일단, enroll과 referral를 사용해서, 각자의 부모 ( 추천자) 가 누구인지 확인할 수 있는 형태의 dictionary를 만들고, 
seller와 amount를 처리한다.

여기서 주의해야할점이있는데, 15원과 같이 남아있을 때, 돈의 처리이다.

15//10을 하면 1원이므로, 부모에게 1원만큼을 넘기고, 자신이 14원을 갖는 형태로 진행해야한다.
이 부분에 대한 아이디어를 생각하지 못하고 문제를 풀다가 , 계속 막혀서 한참 고생했다.

일단 DFS로 문제를 풀었다.

from collections import defaultdict
def mktree(enroll, referral):
    dic=defaultdict()
    for ee, ref in zip(enroll,referral):
        if ref=="-":
            dic[ee] = ['',0]
        else:
            dic[ee]=[ref,0]
    return dic
def solution(enroll, referral, seller, amount):
    dic=mktree(enroll,referral)
    # print(dic)
    for sell,amou in zip(seller,amount):
        coin = amou*100
        forparent=coin//10
        
        if dic[sell][0]=='':# 부모가센터
            dic[sell][1] += coin-forparent
            # print('부모가센터',dic[sell][1])
        
        else: # 다른추천자가있어
            que=[]
            que.append(sell)
            while que:
                now = que.pop()
                # print(now, coin, forparent)
                if now in dic:
                    if coin >= 1:
                        # print(now,':',dic[now][1],'+',round(coin-forparent))
                        dic[now][1] += round(coin-forparent)
                        que.append(dic[now][0])
                        coin = forparent
                        forparent = coin//10
                    else:
                        dic[now][1] += coin
    answer = [int(i[1][1]) for i in dic.items()]
    return answer