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

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

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

 

DFS 알고리즘을 구현하여 가장 하위에 있는 판매원부터 추천인한테 이득을 분배하고 계산된 값을 가지고 더 상위의 추천인한테 이득을 분배하면 된다.

 

예를 들어 center - S - A (a원), B (b원) 로 나타냈을 때 S 는 (a // 10 + b // 10) 이다. 

여기서 center 는 ((a // 10) // 10 + (b // 10) // 10) 이 되는데 원 단위로 절삭하기 때문에 (a // 10 + b // 10) // 10 과는 값이 다르다. 그러므로 (a // 10 + b // 10) 을 result[S] 에 넣어주는 것이 아니라 [a // 10, b // 10] 을 넣고 나중에 sum 을 통하여 계산해준다.

 

10원 보다 작은 이득에 대해서는 추천인한테 줄 돈이 없으므로 10% 계산을 생략해준다. (처리를 안 한다면 시간 초과가 나온다.)

 

 

import sys
from collections import defaultdict

sys.setrecursionlimit(10**8)

def solution(enroll, referral, seller, amount):
    answer = []
    dic = defaultdict(list)
    result = defaultdict(list)
    
    for i in range(len(referral)):
        dic[referral[i]].append(enroll[i])
        
    for i in range(len(seller)):
        result[seller[i]].append(amount[i] * 100)
    
    rf('-', dic, result)
    
    for i in enroll:
        answer.append(sum(result[i]))
    
    return answer
    
def rf(name, dic, result):
    
    for i in dic[name]:
        result[name].extend(rf(i, dic, result))
    
    array = []
    
    if name != '-':
        for i in range(len(result[name])):
            if result[name][i] >= 10:
                array.append(result[name][i] // 10)
                result[name][i] = result[name][i] - (result[name][i] // 10)

    return array
    
print(solution(['john', 'mary', 'edward', 'sam', 'emily', 'jaimie', 'tod', 'young'], ['-', '-', 'mary', 'edward', 'mary', 'mary', 'jaimie', 'edward'], ['young', 'john', 'tod', 'emily', 'mary'], [12, 4, 2, 5, 10])) # [360, 958, 108, 0, 450, 18, 180, 1080]