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

🔗 문제 링크

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

프로그래머스

 

 

📝  풀이

맨 밑단에서부터 수익금을 위쪽으로 분배해주는 방식으로 문제를 풀어야 한다. sam의 수익금중 10%를 edward로 올리고 다시 edward에서 해당 수익금을 mary로 올리고 마지막으로 mary에서 center로 올린다.

 

1. 우선 수익금을 저장하는 memberProfit과 누구로부터 추천을 받았는지 즉, 부모 노드를 저장하는 memberRecommender를 만든다.

memberRecommender = dict() # 추천인 dict에 넣고
    memberProfit = dict() # 수익금
    
    for i in range(len(enroll)):
        memberRecommender[enroll[i]] = referral[i]
        memberProfit[enroll[i]] = 0

2. seller를 순회하면서 수익금을 배분하는데 여기서 DFS 개념을 사용한다. 부모 노드가 '-'가 아닐 때까지 즉, center일 때까지 반복한다. 여기서 부모가 '-'인 경우에도 center로 수익금을 줘야하므로 자신의 수익에서 빼줘야한다.

for i in range(len(seller)):
        cur = seller[i]
        profit = amount[i]*100
        memberProfit[cur] += amount[i]*100
        
        while memberRecommender[cur] != '-': # 부모 노드가 center이 아닐 때까지
            if profit == 0: # 중요!! 
                break
            profit = int(0.1*profit) 
            memberProfit[cur] -= profit # 현재 노드에서 0.1*수익금 빼주고
            memberProfit[memberRecommender[cur]] += profit # 부모노드의 수익금에 더해준다
            cur = memberRecommender[cur]   # 그리고 다시 부모노드를 현재 노드로 교체해서 반복 수행한다
            
        if memberRecommender[cur] == '-': # 부모가 center인 경우 
            memberProfit[cur] -= int(profit*0.1)

여기서 조심해야할게 수익이 0원이 된 경우 더이상 반복문을 돌릴 필요가 없으므로 종료해준다. 해당 조건문 없으면 마지막 3개 테스트 케이스에서 시간 초과 발생한다.

🖥 최종 코드

"""
어느정도 판매가 이루어진 후 누가 얼마만큼의 이득을 가져갔는지
민호 -> center, 8명의 판매원 
모든 판매원은 칫솔의 판매에 의하여 발생하는 이익에서 10%를 계산하여 자신을 조직에 참여시킨 추천인에게 배분하고 나머지 가짐
모든 판매원은 자신이 칫솔판매에서 발생한 이익뿐만아니라 가입시킨 판매워 10%까지 자기 이익
enroll -> 민호를 제외한 조직원 
referral
i번째 이름 
"""

def solution(enroll, referral, seller, amount):
    result = []
    memberRecommender = dict() # 추천인 dict에 넣고
    memberProfit = dict() # 수익금
    
    for i in range(len(enroll)):
        memberRecommender[enroll[i]] = referral[i]
        memberProfit[enroll[i]] = 0
        
    for i in range(len(seller)):
        cur = seller[i]
        profit = amount[i]*100
        memberProfit[cur] += amount[i]*100
        while memberRecommender[cur] != '-':
            if profit == 0:
                break
            profit = int(0.1*profit)
            memberProfit[cur] -= profit
            memberProfit[memberRecommender[cur]] += profit
            cur = memberRecommender[cur]    
        if memberRecommender[cur] == '-':
            memberProfit[cur] -= int(profit*0.1)
    for member in enroll:
        result.append(memberProfit[member])
    return result