[프로그래머스] 다단계 칫솔 판매

문제

• 한 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배된다.
  • 판매에 의해 발생하는 이익에서 10%를 계산해 자신을 조직에 참여시킨 추천인에게 배분한다.
  • 모든 판매원은 자신이 칫솔 판매에서 발생한 이익과 자신이 조직에 추천해 가입시킨 판매원에게서 발생한 이익의 10% 까지 자신의 이익이 된다.
  • 단, 10%를 계산할 때는 원 단위에서 절사하고 10%를 계산한 금액이 1원 미만인 경우 이득을 분배하지 않는다.
• 모든 판매원의 칫솔 판매이익금이 주어질 때, 각 판매원이 득한 이익금을 계산해 리턴하기
  • 1 <= 판매원 수 <= 10,000

 

풀이

• 트리 구조로 나타낼 때, 리프 노드에서 시작해 자신의 이익금을 부모에게 전달해야 한다.
• 이 과정에서 전체 판매원의 수가 최대 만 명이고 일렬로 늘어져 있다면, $O(N^2)$ 시간이 걸린다.
  -> 아마도 이런 테스트 케이스는 없을 것 같다.
• 부모에게 이익금 전달할 때, 부모가 없거나 더이상 이익금을 나눌 수 없는 경우 stop.

 

from collections import defaultdict

# 부모에게 이익금 전달하기
def calc(me, money, answer, tree) :
        if me == '-' :  # 더이상 부모가 없는 경우 stop
            return
        
        if money < 10 : # 더이상 이익금을 나눌 수 없는 경우 stop
            answer[me] += money
        else :          
            # 이익금의 90%는 내가 가지고,
            answer[me] += money - int(money * 0.1)  
            # 10%는 부모에게 전달하기
            calc(tree[me], int(money * 0.1), answer, tree)
            
def solution(enroll, referral, seller, amount):
    answer = dict()     # 사람별 수익금
    tree = dict()       # tree[me] = parent
    for me, parent in zip(enroll, referral):
        tree[me] = parent
        answer[me] = 0
    
    for me, money in zip(seller, amount) :
        calc(me, money * 100, answer, tree)
    
    return [ answer[name] for name in enroll ]

 

References

• 프로그래머스 Lv3 다단계 칫솔 판매