[Programmers] Lv3. 다단계 칫솔 판매

문제 링크 

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

문제설명

민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, 조직을 운영하던 민호는 조직 내 누가 얼마만큼의 이득을 가져갔는지가 궁금해졌습니다. 예를 들어, 민호가 운영하고 있는 다단계 칫솔 판매 조직이 아래 그림과 같다고 합시다.

민호는 center이며, 파란색 네모는 여덟 명의 판매원을 표시한 것입니다. 각각은 자신을 조직에 참여시킨 추천인에 연결되어 피라미드 식의 구조를 이루고 있습니다. 조직의 이익 분배 규칙은 간단합니다. 모든 판매원은 칫솔의 판매에 의하여 발생하는 이익에서 10% 를 계산하여 자신을 조직에 참여시킨 추천인에게 배분하고 나머지는 자신이 가집니다. 모든 판매원은 자신이 칫솔 판매에서 발생한 이익 뿐만 아니라, 자신이 조직에 추천하여 가입시킨 판매원에게서 발생하는 이익의 10% 까지 자신에 이익이 됩니다. 자신에게 발생하는 이익 또한 마찬가지의 규칙으로 자신의 추천인에게 분배됩니다. 단, 10% 를 계산할 때에는 원 단위에서 절사하며, 10%를 계산한 금액이 1 원 미만인 경우에는 이득을 분배하지 않고 자신이 모두 가집니다.

각 판매원의 이름을 담은 배열 enroll, 각 판매원을 다단계 조직에 참여시킨 다른 판매원의 이름을 담은 배열 referral, 판매량 집계 데이터의 판매원 이름을 나열한 배열 seller, 판매량 집계 데이터의 판매 수량을 나열한 배열 amount가 매개변수로 주어질 때, 각 판매원이 득한 이익금을 나열한 배열을 return 하도록 solution 함수를 완성해주세요. 판매원에게 배분된 이익금의 총합을 계산하여(정수형으로), 입력으로 주어진 enroll에 이름이 포함된 순서에 따라 나열하면 됩니다.

 

문제해설

enroll, referral, seller, amount의 정보를 가지고 트리구조를 잘 구현할 수 있는지를 묻는 문제이다.

정확히는 각 노드가 자식 노드의 정보가 아닌 부모 노드의 정보를 포함하도록 구현하면, 원하는 노드에서 위로 올라가며 수익을 배분하도록하여 문제를 풀 수 있다.

이때, 주의할 점은 이익의 10%가 0이 되면, 더이상 부모노드로 이익을 올려보내지 않고 종료해야 한다는 점이다.

enroll이 최대 10000, seller가 100000까지의 숫자이기 떄문에, 만약 트리의 구조가 일자로 나열된 편향이진트리일 경우 최악의 경우 10000*100000의 cost가 발생한다.

또한, seller의 매 판매마다 배분을 진행해야한다. 만약 판매금을 모아서 한번에 배분을 진행할 경우, 요구사항과는 다른 닶이 나올 것이다. ex)5원,5원은 위로 올릴 배분금이 없지만, 합쳐서 10원이 되면 1원을 배분해야 한다.

 

여기서는 트리를 생성하기 위해 파이썬의 zip을 사용했다. 각 사원의 수익을 저장하는 sell_d와 각 사원의 추천인을 저장하는 referral_d를 생성하고 초기화하여 1번의 스캔을 통해 dictionary를 초기화했다.

이후, 각 판매마다 판매금의 10%를 빼고 상위로 올려보내는 반복문을 추천인이 없을 때까지 반복했다.

def solution(enroll, referral, seller, amount):
    answer = []
    sell_d = {}
    referral_d = {}
    for idx,(e,r) in enumerate(zip(enroll,referral)):
        sell_d[e]=0
        referral_d[e]=r
    for sell,amount in zip(seller,amount):
        remain_money = amount*100
        pivot = sell
        while pivot != '-':
            upload_money = remain_money//10
            remain_money -= upload_money
            sell_d[pivot] += remain_money
            pivot = referral_d[pivot]
            remain_money = upload_money
            if remain_money == 0:
                break
    answer = list(sell_d.values())
        
    return answer