[프로그래머스] 다단계 칫솔 판매 - 파이썬

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

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

문제 설명

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

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

예를 들어, 아래와 같은 판매 기록이 있다고 가정하겠습니다. 칫솔의 판매에서 발생하는 이익은 개당 100 원으로 정해져 있습니다.

판매원판매 수량이익금

young	12	1,200 원
john	4	400 원
tod	2	200 원
emily	5	500 원
mary	10	1,000 원

판매원 young 에 의하여 1,200 원의 이익이 발생했습니다. young 은 이 중 10% 에 해당하는 120 원을, 자신을 조직에 참여시킨 추천인인 edward 에게 배분하고 자신은 나머지인 1,080 원을 가집니다. edward 는 young 에게서 받은 120 원 중 10% 인 12 원을 mary 에게 배분하고 자신은 나머지인 108 원을 가집니다. 12 원을 edward 로부터 받은 mary 는 10% 인 1 원을 센터에 (즉, 민호에게) 배분하고 자신은 나머지인 11 원을 가집니다. 이 상태를 그림으로 나타내면 아래와 같습니다.

그 후, 판매원 john 에 의하여 400 원의 이익이 발생합니다. john 은 10% 인 40 원을 센터에 배분하고 자신이 나머지인 360 원을 가집니다. 이 상태를 그림으로 나타내면 아래와 같습니다.

또 그 후에는 판매원 tod 에 의하여 200 원 이익이 발생하는데, tod 자신이 180 원을, 추천인인 jaimie 가 그 중 10% 인 20 원을 받아서 18 원을 가지고, jaimie 의 추천인인 mary 는 2 원을 받지만 이것의 10% 는 원 단위에서 절사하면 배분할 금액이 없기 때문에 mary 는 2 원을 모두 가집니다. 이 상태를 그림으로 나타내면 아래와 같습니다.

그 다음으로 emily 가 칫솔 판매를 통하여 얻은 이익 500 원은 마찬가지의 규칙에 따라 emily 에게 450 원, mary 에게 45 원, 그리고 센터에 5 원으로 분배됩니다. 이 상태를 그림으로 나타내면 아래와 같습니다.

마지막으로, 판매원 mary 는 1,000 원의 이익을 달성하고, 이 중 10% 인 100 원을 센터에 배분한 후 그 나머지인 900 원을 자신이 가집니다. 이 상태를 그림으로 나타내면 아래와 같습니다.

위와 같이 하여 모든 조직 구성원들의 이익 달성 현황 집계가 끝났습니다. 지금까지 얻은 이익을 모두 합한 결과를 그림으로 나타내면 아래와 같습니다.

이 결과가 민호가 파악하고자 하는 이익 배분 현황입니다.

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

---

풀이

enroll, seller의 최대 길이는 각각 10,000 100,000 입니다. 즉 두 배열을 이중 순회하며 순차적으로 탐색하는 경우는 시간초과가 발생합니다. 저도 처음에 index 함수를 사용하여 인덱스를 찾는 방식으로 탐색했는데 10, 11, 12, 13 케이스에서 시간초과가 발생했습니다.

따라서 dictionary를 이용하여 본인의 인덱스를 찾는 과정은 O(1)로 해결해야합니다. enroll 리스트를 순회하며 본인의 인덱스와 함께 딕셔너리에 저장하여 사용하면 됩니다.

 

가격을 계산하는 과정에서 주의할 점은 본인의 수익은 반드시 10%를 빼고 계산해야한다는 점입니다. 부모 노드로 넘겨야 할 가격은 10%가 빼지지 않은 기존 가격 price의 10%를 넘겨야 합니다.

 

price가 0이 되는 경우(1보다 작은 경우)는 더 이상 의미없는 계산이므로 종료합니다.

-> 해당 과정을 수행하지 않으면 11, 12, 13 케이스에서 시간초과가 발생합니다.

 

 

def solution(enroll, referral, seller, amount):
    answer = []
    prices = [] # 수익을 기록하는 배열
    d = {}

    for i in range(len(enroll)):
        prices.append(0)
        d[enroll[i]] = i
    
    for i in range(len(seller)):
        name = seller[i] 
        price = amount[i] * 100
        
        while True:
            ind = d[name] # 본인 번호 찾기
            recom_name = referral[ind] # 추천인 찾기
            
            if recom_name == '-': # 루트 노드에 연결되어있으면 종료, 마지막 사람도 계산
                add = price - (price // 10)
                prices[ind] += add
                break
                
            else:
                add = price - (price // 10)
                prices[ind] += add
                price = price // 10
                
                name = recom_name # 탐색할 사람 최신화
                if price < 1: # 가격이 0이 나오는 경우 종료(더 이상 의미없음)
                    break
                    
    answer = prices
    return answer