[Programmers] Level 3. 다단계 칫솔 판매

🔗 Problem Link

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

프로그래머스

---

❔Thinking

• 트리 형식의 다단계 관계가 주어지면, 조건에 맞게 이익을 계산해 최종 이익금을 반환한다.
• 10%를 자신을 추천한 사람에게 떼어주고, 10%한 금액이 1원 미만인 경우는 본인이 전액을 가진다.

---

💻Solution

def solution(enroll, referral, seller, amount):
    n = len(enroll)
    tree = {}
    money = {}
    for i in range(n):
        tree[enroll[i]] = referral[i]  
        money[enroll[i]] = 0
        
    def dfs(name, benefit):
        if name == '-':
            return
        if int(benefit*0.1) >= 1:
            money[name] += benefit - int(benefit*0.1)
            dfs(tree[name], int(benefit*0.1))
        else:
            money[name] += benefit
            return
        
    for s, a in zip(seller, amount):
        dfs(s, a*100)
        
    return list(money.values())

---

🗝️keypoint

1. 이익의 10%를 내림하여 계산하고, 이 금액이 1원 미만인 경우에는 본인이 전액을 가지도록 구성한다.
2. dfs를 통해 트리의 부모를 찾아가는 형태를 구성하고, 본부(center)에 도달한 '-'인 경우를 종료 조건으로 한다.
3. list의 index는 시간복잡도상 시간초과가 발생할 수 있기 때문에, dict 형태를 활용한다.
4. python의 dict.values()는 순서가 유지된 list를 반환한다.