[프로그래머스] 다단계 칫솔 판매 [Python(파이썬)]

문제

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

코딩테스트 연습 - 다단계 칫솔 판매

 

풀이

트리 구조로 입력이 주어지지만, 딱히 트리 구조를 구현할 필요는 없는 구현 문제였다. 부모 노드를 통해서 조상 노드를 계속해서 탐색하며, 수익을 계산해주면 된다. 이때, 수익을 계산하는 방식을 눈여겨봐야한다. 

 

조상 노드부터 현재 노드까지의 서브 트리가 가질 수 있는 총 수익을 total_profit이라고 할 때,

※ total_profit은 매 탐색마다 갱신된다!
조상 노드의 수익: total_profit *0.1
현재 노드의 수익: total_profit * 0.9

이라고 문제를 풀면 틀린다.

 

문제에서 주어진 예시에서 수익을 분배하는 문장을 잘 보자.

 edward 는 young 에게서 받은 120 원 중 10% 인 12 원을 mary 에게 배분하고 자신은 나머지인 108 원을 가집니다. 12 원을 edward 로부터 받은 mary 는 10% 인 1 원을 센터에 (즉, 민호에게) 배분하고 자신은 나머지인 11 원을 가집니다.

 

 

즉, 조상 노드의 수익을 먼저 계산한 후 자신은 그 나머지를 취하는 방식이다. 이를 식으로 표현하면 다음과 같다.

조상 노드의 수익: total_profit * 0.1
현재 노드의 수익: total_profit - 부모 노드의 수익

 

이 부분만 신경 써준다면 간단하게 풀 수 있는 문제였다.

 

코드

def solution(enroll, referral, seller, amount):
    PRICE_OF_TOOTHBRUSH = 100
    ANCESTOR_PROFIT_RATIO = 0.1

    answer = []
    parent_dict = dict(zip(enroll, referral))
    profit_dict = {key: 0 for key in enroll}
    
    for i, sell_amount in enumerate(amount):
        current = seller[i]
        parent = parent_dict[current]

        total_profit = sell_amount * PRICE_OF_TOOTHBRUSH 
        ancestor_profit = int(total_profit * ANCESTOR_PROFIT_RATIO)
        own_profit = total_profit - ancestor_profit

        profit_dict[current] += own_profit

        while parent != "-" and ancestor_profit >= 1:
            total_profit = ancestor_profit
            ancestor_profit = int(total_profit * ANCESTOR_PROFIT_RATIO)
            own_profit = total_profit - ancestor_profit
            
            current, parent = parent_dict[current], parent_dict[parent]
            
            profit_dict[current] += own_profit
    
    answer = list(profit_dict.values())

    return answer