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

문제를 정리해보자.

 

 

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

 

 

위 판매망은 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태이다.

각각은 자신을 조직에 참여시킨 추천인에게 연결되어 피라미드식의 구조를 이루고 있다.

조직의 이익 분배 규칙은 다음과 같다.

 

1. 이익에서 10%를 계산하여 자신을 조직에 참여시킨 추천인에게 배분하고 나머지는 자신이 가진다.

+ 모든 판매원은 자신이 칫솔 판매에서 발생한 이익뿐만 아니라, 자신이 조직에 추천하여 가입시킨 판매원에게서 발생하는 이익의 10%까지 자신에 이익이 된다.

+ 자신에게 발생하는 이익 또한 마찬가지의 규칙으로 자신의 추천인에게 분배된다

 

2. 단, 10%를 계산할 때는 원 단위에서 절사한다. 그리고 10%를 계산한 금액이 1원 미만인 경우에는 이득을 분배하지 않고 자신이 모두 가진다.

 

 

---

풀이를 생각해보자.

 

예를 들어, 아래와 같은 판매 기록이 있다고 가정하자.

(칫솔의 판매에서 발생하는 이익은 개당 100원으로 정해져 있다.)

 

 

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

 

 

 

그러면 아래와 같은 결과가 파악하고자 하는 이익 배분 현황이 된다.

 

 

 

이 현황을 구하는 방법은 2가지로 예상된다.

 

1. 이익이 발생할 때마다 이익을 분배한다.

2. 이익을 누적시켰다가 한번에 분배한다. (합산X)

 

아래는 두 번째 방법의 설계도이다.

 

 

두 번째 방법 설계

 

 

---

 

각각 장단점

 

첫 번째 방법)

 

이 문제의 핵심은 다음과 같다.

1. '10%를 계산한 금액이 1원 미만인 경우에는 이득을 분배하지 않고 자신이 모두 가진다.'

2. 판매량 범위는 1이상 100이하의 자연수이다. (따라서 판매 최대이득은 10,000이다.)

 

1원 미만인 경우는 재귀가 돌 필요가 없다. 따라서 재귀가 무조건 1000번 이하로 끝난다.

하지만 노드 재방문이 많다.

 

 

두 번째 방법)

 

노드를 재방문하지 않는다는 장점이 있다.

하지만 파이썬은 재귀 깊이가 1,000으로 제한되어 있다. 

이 문제를 보면 판매원이 최대 10,000명까지 존재한다.

따라서 직선 트리의 경우 재귀의 깊이가 10,000까지 가게 된다.

따로 제한을 풀어주지 않으면 통과할 수 없다.

 

 

---

구현해보자

 

두 번째 방법으로 구현했다.

 

 

import math
import sys
sys.setrecursionlimit(100000)  # 직선 트리

# DFS
def dfs(tree, start_name, check, money):
    check[start_name] = 1

    for name in tree[start_name]:
        if check[name] == 0:
            money[start_name] += dfs(tree, name, check, money)

    # 10% 계산
    tmp = []
    for idx, cal_money in enumerate(money[start_name]):
        cal = math.trunc(cal_money * 0.1)
		
        # 1원 미만은 추가에 제한
        if cal > 0:
            money[start_name][idx] -= cal
            tmp.append(cal)

    return tmp


def solution(enroll, referral, seller, amount):

    l = len(enroll)
    tree = {'-': []}
    check = {'-': 0}
    money = {'-': [0]}

    # 트리 생성
    for i in range(l):
        parent = referral[i]
        child = enroll[i]

        check[child] = 0
        money[child] = [0]

        if not tree.get(child, 0):
            tree[child] = []

        tree[parent].append(child)

    # 판매량 집계 데이터의 판매 수량 (합산 판매 X)
    for idx, name in enumerate(seller):
        money[name].append(amount[idx] * 100)

    # DFS
    dfs(tree, '-', check, money)

    # 결과
    answer = []
    for name in enroll:
        answer.append(sum(money[name]))
    return answer


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]))

 

 

---

 

시행착오

 

이득은 얻을 때마다 추천인과 분배하는 것이다. 얻은 이득을 합산해서 추천인과 분배하면 완전 다른 값이 나온다.