프로그래머스 Python - [트리] 다단계 칫솔 판매

프로그래머스
트리 - 다단계 칫솔 판매
2021 Dev-Matching: 웹 백엔드 개발자(상반기)

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

설계

테스트 케이스 중 한명의 seller를 선택하여 도식(트리 구조)을 그려보면
연산식을 쉽게 구할 수 있다.

이익의 90%를 자식 노드가 가져가고 10%가 부모 노드에 분배된다.

단 중요한 조건이 있는데, 1원 미만이면 이득을 분배하지 않고 자신이 모두 가진다고 명시 되어있다. 즉 소숫점 이하의 금액은 모두 버려지므로 /(나눗셈)가 아닌 //(몫만 계산)을 사용한다.

total += money - (money // 10) # 이익금의 총합
money = money // 10

💡Key Idea
딕셔너리와 해시를 이용하여 풀이하도록 한다.
딕셔너리는 다음과 같이 2개 생성하였다.

1. parent
   key: enroll(자식노드)
   value: referral(부모노드)
2. total
   key: 판매자
   value: 판매수익
   -> 판매자는 문제에서 제시한대로 enroll 리스트 순서대로 나열

코드

def solution(enroll, referral, seller, amount):
    parent = dict(zip(enroll, referral))

    total = {name: 0 for name in enroll}

    for i in range(len(seller)):
        money = amount[i] * 100
        cur_name = seller[i]

        while money > 0 and cur_name != '-':
            total[cur_name] += money - (money // 10)
            cur_name = parent[cur_name]
            money //= 10

    return [total[name] for name in enroll]

테스트

• Input

def main():
    # 테스트 케이스 1
    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]))
    # 테스트 케이스 2
    print(solution(["john", "mary", "edward", "sam", "emily", "jaimie", "tod", "young"],
                   ["-", "-", "mary", "edward", "mary", "mary", "jaimie", "edward"],
                   ["sam", "emily", "jaimie", "edward"],
                   [2, 3, 5, 4]))


if __name__ == "__main__":
    main()

• 결과