문제 설명
•
추천 관계로 이루어진 다단계 조직에서 각 판매원이 얻을 수 있는 이익을 계산하는 문제
◦
모든 판매원은 칫솔 판매로 발생한 이익의 10%를 추천인에게 배분하고, 나머지 금액을 자신이 갖는다.
◦
각 판매원은 자신의 판매 이익뿐만 아니라, 자신이 추천한 하위 판매원들이 발생시킨 이익의 10%도 추가로 획득한다.
◦
10%를 계산할 때는 원 단위에서 절사하며, 10%의 금액이 1원 미만일 경우에는 분배하지 않고 자신이 모두 가진다.
예제 입력/출력
enroll | referral | seller | amount | result |
["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] |
["john", "mary", "edward", "sam", "emily", "jaimie", "tod", "young"] | ["-", "-", "mary", "edward", "mary", "mary", "jaimie", "edward"] | ["sam", "emily", "jaimie", "edward"] | [2, 3, 5, 4] | [0, 110, 378, 180, 270, 450, 0, 0] |
제약 조건
•
•
•
•
◦
판매량의 범위
문제 풀이
접근1 문제에서 시키는 대로 단순 구현 -
접근2 시간 복잡도 줄이기 -
접근3 시간 복잡도 줄이기 -
풀이 코드
def query(name, price):
global money, tree
price10 = int(price * 0.1)
money[name] += price - price10
if price10 == 0:
return
if name != '-':
query(tree[name], price10)
def solution(enroll, referral, seller, amount):
global money, tree
money = dict()
money['-'] = 0
for name in enroll:
money[name] = 0
tree = dict()
for child, parent in zip(enroll, referral):
tree[child] = parent
for name, num in zip(seller, amount):
query(name, num * 100)
ans = [money[name] for name in enroll]
return ans
Python
복사