[프로그래머스] Lv.3 | 다단계 칫솔 판매 (Python)

🪥 다단계 칫솔 판매

정답률 41% | 저자 권장 시간 60분 | 권장 시간 복잡도 O(N²) | 출제 2021 Dev-Matching: 웹 백엔드 개발자(상반기)
문제 URL

문제 설명

민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 분배됩니다. 모든 판매원은 칫솔의 판매에 의하여 발생하는 이익에서 10%를 자신을 조직에 참여시킨 추천인에게 배분하고, 나머지는 자신이 가집니다. 이익 배분 과정은 반복적으로 이루어집니다.

예시

입력

• enroll: ["john", "mary", "edward", "sam", "emily", "jaimie", "tod", "young"]
• referral: ["-", "-", "mary", "edward", "mary", "mary", "jaimie", "edward"]
• seller: ["young", "john", "tod", "emily", "mary"]
• amount: [12, 4, 2, 5, 10]

판매 기록

판매원	판매 수량	이익금
young	12	1,200
john	4	400
tod	2	200
emily	5	500
mary	10	1,000

이익 분배 과정

1. young이 1,200원 이익 발생:

   • young: 1,080원 (90%)
   • edward: 120원 (10%)
   • edward: 108원 (90%) + mary: 12원 (10%)
   • mary: 11원 (90%) + center: 1원 (10%)

2. john이 400원 이익 발생:

   • john: 360원 (90%)
   • center: 40원 (10%)

3. tod가 200원 이익 발생:

   • tod: 180원 (90%)
   • jaimie: 20원 (10%)
   • jaimie: 18원 (90%) + mary: 2원 (10%)

4. emily가 500원 이익 발생:

   • emily: 450원 (90%)
   • mary: 45원 (10%)
   • mary: 41원 (90%) + center: 4원 (10%)

5. mary가 1,000원 이익 발생:

   • mary: 900원 (90%)
   • center: 100원 (10%)

최종 이익 분배 결과

판매원	최종 이익금
john	360
mary	958
edward	108
sam	0
emily	450
jaimie	18
tod	180
young	1,080

---

💻나의 풀이

def pyramid(seller, amount, recommend, answer):
    for i in range(len(seller)):
        name = seller[i]
        money = amount[i] * 100
        
        while name != "-" and money >= 1:
            commission = money // 10
            answer[name] += (money - commission)
            money = commission
            name = recommend[name]

def solution(enroll, referral, seller, amount):
    recommend = {}
    answer = {}

    for i in range(len(enroll)):
        recommend[enroll[i]] = referral[i]
        answer[enroll[i]] = 0

    pyramid(seller, amount, recommend, answer)

    return [answer[name] for name in enroll]

시간 복잡도: O(N * M)

코드 설명

def pyramid(seller, amount, recommend, answer):
    # 각 판매자와 판매량을 순회
    for i in range(len(seller)):
        name = seller[i]  # 현재 판매자의 이름
        money = amount[i] * 100  # 판매 이익 (칫솔 한 개당 100원)

        # 추천인 체계에 따라 이익을 분배
        while name != "-" and money >= 1:
            commission = money // 10  # 추천인에게 줄 커미션 (10%)
            answer[name] += (money - commission)  # 현재 판매자가 가져갈 이익
            money = commission  # 추천인에게 줄 금액으로 갱신
            name = recommend[name]  # 다음 추천인으로 이동

def solution(enroll, referral, seller, amount):
    recommend = {}  # 추천인 정보를 저장할 딕셔너리
    answer = {}  # 각 판매자가 얻은 이익을 저장할 딕셔너리

    # enroll과 referral을 순회하며 추천인 정보를 설정
    for i in range(len(enroll)):
        recommend[enroll[i]] = referral[i]
        answer[enroll[i]] = 0  # 초기 이익을 0으로 설정

    # 판매 데이터를 기반으로 이익을 계산
    pyramid(seller, amount, recommend, answer)

    # 결과를 enroll의 순서에 맞춰 반환
    return [answer[name] for name in enroll]

처음 문제를 봤을 때부터 추천인이 없을 때까지 반복해야 된다는 것은 알았지만 좀처럼 쉽게 구현되지 않았다. 나는 추천인 구조를 반복하는 pyramid 함수를 따로 만들어 구현했는데, 조금 더 나은 방법이 있었을 것 같아 아쉬운 코드이다.

---

✔️ 정답 코드

def solution(enroll, referral, seller, amount):
    # ➊ parent 딕셔너리 key는 enroll의 노드, value는 referral의 노드로 구성됨
    parent = dict(zip(enroll, referral))

    # ➋ total 딕셔너리 생성 및 초기화
    total = {name: 0 for name in enroll}

    # ➌ seller 리스트와 amount 리스트를 이용하여 이익 분배
    for i in range(len(seller)):
        # ➍ 판매자가 판매한 총 금액 계산
        money = amount[i] * 100
        cur_name = seller[i]
        # ➎ 판매자부터 차례대로 상위 노드로 이동하며 이익 분배
        while money > 0 and cur_name != "-":
            # ➏ 현재 판매자가 받을 금액 계산(10%를 제외한 금액)
            total[cur_name] += money - money // 10
            cur_name = parent[cur_name]
            # ➐ 10%를 제외한 금액 계산
            money //= 10

    # ➑ enroll 리스트의 모든 노드에 대해 해당하는 이익을 리스트로 반환
    return [total[name] for name in enroll]

시간 복잡도: O(N * M)

• N: enroll의 길이
• M: seller의 길이
  seller별로 enroll을 탐색하므로 시간 복잡도는 O(N * M)이다.

문제 분석 & 코드 설명

판매자-추천인의 관계 = 부모-자식 관계 -> 트리

1) parent 딕셔너리 생성

현재 판매원(enroll)을 기준으로 추천인(referral)에게 이익금을 주는 연산이 반복되므로 enroll:referral인 딕셔너리를 생성해야 한다.

parent = dict(zip(enroll, referral))

여기서 zip() 함수는 이터러블한 객체를 인수로 받아 동일한 인덱스에 위한 노드를 묶어 튜플로 반환한다.

fruits = ['apple', 'banana', 'cherry']
prices = [1000, 2000, 3000]
print(list(zip(fruits, prices)))
# [('apple', 1000), ('banana', 2000), ('cherry', 3000)]

2) total 딕셔너리 생성

total = {name: 0 for name in enroll}

또한 문제에서 요구한 것은 각 판매자의 수익 총액이므로 수익들의 누적값이 필요하다. 이는 판매자들의 이름을 키로 하고 판매 수익을 값으로 하는 딕셔너리를 만들어 쉽게 해결할 수 있다.

3) 판매자(seller) 리스트 순회

for i in range(len(seller)):

본격적으로 seller 리스트와 amount 리스트를 이용하여 이익 분배를 시작한다.

4) 판매자가 판매한 총 금액 계산

money = amount[i] * 100
cur_name = seller[i]

이때, amount[i]는 seller[i]가 판매한 칫솔의 개수이다. 칫솔 하나당 수익은 100원이므로 판매자가 번 수익은 amount[i] * 100이다.

또한 cur_name은 현재 판매자의 이름을 참조하고 있다.

5) 판매자부터 차례대로 상위 노드로 이동하며 이익 분배

while money > 0 and cur_name != "-":

현재 판매자의 추천자에게 10%의 수익금을 분배한다. 재귀로 구현하여 거슬러 올라갔을 때 추천자가 없을 때까지 반복한다.

6) 현재 판매자가 받을 금액 계산(10%를 제외한 금액)

total[cur_name] += money - money // 10
cur_name = parent[cur_name]

현재 판매자는 현재 수익에서 수익금의 10%를 추천인에게 분배하고 나머지를 수익금으로 생각한다. 수익금을 얻고 나면 cur_name을 자신의 부모(추천인)으로 변경한다.

7) 10%를 제외한 금액 계산

money //= 10

cur_name이 추천인으로 바뀌면 마찬가지로 money도 부모 기준에 맞춰 원래 money의 10% 금액으로 변경한다.

8) 결과 반환

return [total[name] for name in enroll]

enroll 리스트의 모든 노드에 대해 해당하는 이익을 리스트로 반환한다.