[Python] 프로그래머스 77486. 다단계 칫솔 판매 (Lv.3)

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

프로그래머스

 

기본적인 DFS로 구현이 가능한 문제입니다.

입력에 따라 판매원들의 이름을 Dictionary에 저장해서 Index화 해줍니다. 

이후 판매원들의 referral을 입력받아 자신을 초대한 사원을 가리키게 해주면 위로만 타고 올라가지는 그래프 형태의 구조가 됩니다.

이제 매출이 발생한 입력마다 위로 타고 올라가며 상납금(?)을 더해주면 됩니다.

 

11~13번에서 런타임 에러가 발생한다면 해당 테스트케이스의 사원들의 초대 형태가 일렬로 길게 이어진 모양이라 타고 올라가다가 스택 오버플로우가 발생한 것입니다.

종료조건이 제대로 잡히지 않았을때 자주 발생하는 에러인데, 생각해 보면 판매에서 얻어지는 이익의 최댓값은 10000입니다. (칫솔 하나의 이익이 100원, 판매수의 최대가 100)

상납금은 10%씩을 납부하는데, 가장 큰 이익이 발생해도 몇 단계만 올라가면 상납금은 0원이 됩니다.

10000 (매출 발생) -> 1000원 상납 -> 100원 상납 -> 10원 상납 -> 1원 상납 -> 0원 상납 (판매자의 5단계 위는 돈을 얻을 수 없다!)

 

따라서 상납금이 0원이 되는 경우 다음 호출을 하지 않도록 탈출 조건을 잡아주면 됩니다.

if lead == -1 or tax == 0: (돈을 보낼 초대자가 존재하지 않거나, 보낼 돈이 0원일시 더 이상 호출하지 않음)

 

def solution(enroll, referral, seller, amount):
    result = [0 for i in range(len(enroll))]
    follow = [-1 for i in range(len(enroll))]
    name_dict = {}

    index = 0
    for name in enroll:
        name_dict[name] = index
        index += 1

    for i in range(len(referral)):
        if referral[i] != '-':
            target = name_dict[referral[i]]
            follow[i] = target

    for i in range(len(seller)):
        start = name_dict[seller[i]]
        money = amount[i] * 100
        send_money(follow, result, money, start)

    return result


def send_money(follow, result, money, me):
    lead = follow[me]
    tax = int(money / 10)
    result[me] += money - tax

    if lead == -1 or tax == 0:
        return
    else:
        send_money(follow, result, tax, lead)