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

🔗

풀이

순환구조가 없는 그래프 형태이므로 트리 구조라고 볼 수 있다. 판매원을 자식이라하면 판매원을 소개시켜준 사람은 부모가 된다. 즉, 자식 노드가 얻은 이득의 10%를 부모가 갖게된다. 이 과정은 루트 노드에 도달할 때까지 반복한다라는 게 된다.

총 판매원은 1만명까지 존재할 수 있고, 편향트리라고 해도 1만 번이지만 애초에 벌어들이는 금액이 1만이 최대라 최대 10번을 넘기기도 힘들다. 아무튼 이득을 얻은 판매원의 부모 노드로 10%를 보내고, 보낸 10%의 90%만 그 부모 노드에 저장하고 다시 10%는 그 부모 노드의 부모 노드로 보내는 방식을 반복문으로 구현해서 풀었다.

parent 딕셔너리의 경우 {자식: 부모} 형태로 저장되는데, 자식 입장에서 부모가 누구인지만 알면되기 때문이다. 부모 입장에서는 어떤 자식과 연결되는지 몰라도 되는 상태.

def solution(enroll, referral, seller, amount):
    parent = defaultdict(lambda: '')
    profit = defaultdict(int)
   
    # 부모-자식 정보 저장
    for i in range(len(enroll)):
        parent[enroll[i]] = referral[i]
    
    # 반복문으로 자식에서 10%씩 부모에게 전달
    for j in range(len(seller)):
        i_amount = amount[j]*100
        i_seller = seller[j]
        while True:
            rem = int(i_amount*0.1)
            profit[i_seller] += i_amount-rem
            if not parent[i_seller] or not rem:
                break
                
            i_amount, i_seller = rem, parent[i_seller]
    
    answer = []
    for name in enroll:
        answer.append(profit[name])
    
    return answer
from collections import defaultdict