[프로그래머스] 다단계 칫솔 판매 - Level 3 (Python)

📌 문제 정보

다단계 칫솔 판매 Level 3

플랫폼

프로그래머스

유형

트리, 해시, 시뮬레이션

언어

Python 3

풀이 시간

약 70분

풀이 날짜

2026.05.04

문제 링크

바로가기 ↗

---

🧩 문제 요약

다단계 판매 조직(enroll, referral)에서 각 판매원(seller)이 칫솔을 판매(amount)했을 때, 추천인 체인을 따라 10%씩 이익을 분배하며 각 판매원이 최종적으로 가져가는 금액을 구하는 문제

핵심 조건:

• 판매원은 본인 판매금의 10%를 자신의 추천인에게 지급
• 추천인도 그 금액의 10%를 자신의 추천인에게 지급 (재귀적으로 반복)
• 분배할 금액이 1원 미만이면 그 윗단계로는 분배하지 않고, 자신이 갖음
• 최상위 조직("-")은 더 이상 분배하지 않고 받기만 함

입력 조건:

• 가입한 사람 수: 2 ≤ enroll의 길이 ≤ 10,000
• enroll, referral, seller, amount는 모두 대응하는 길이 규칙을 가짐
• 판매 금액: 1 ≤ amount 원소 ≤ 100,000

출력 조건:

• enroll 순서대로 각 판매원이 최종적으로 받은 금액 배열 반환

---

💡 나의 접근 방식

1단계 - 처음 든 아이디어

부모(추천인)를 알아야 분배가 가능한 구조이므로, 자식 → 부모 방향 트리가 필요하다고 판단했다. 처음엔 (부모, 가격) 튜플로 묶을지 고민했지만, 가독성을 위해 {이름: {'parent': 부모, 'price': 가격}} 형태의 딕셔너리로 설계했다.

2단계 - 막혔던 부분

while 루프에서 다음 노드로 올라갈 때 current = dict[p]['parent']로 한 단계를 건너뛰는 실수를 했다. p(부모)는 이미 처리가 끝난 노드인데, 그다음 반복에서는 p의 부모가 아니라 p 자신부터 처리해야 한다는 걸 놓쳤다.

또한 최상위 조직("-")에 도달했을 때, while 조건 때문에 루프에 아예 진입하지 못해 정작 최상위 직속 판매원 본인의 10% 차감이 누락되는 문제도 있었다.

3단계 - 해결 실마리

• current = p 로 수정하여 정확히 한 단계씩만 올라가도록 변경
• while 루프를 빠져나온 후 earn >= 1이면 마지막으로 한 번 더 차감하는 로직 추가 → 최상위 직속 판매원의 10% 차감 누락 해결
• earn < 1이면 그 윗단계로는 분배하지 않고 break

핵심 아이디어:

• 자식 → 부모 방향 트리는 딕셔너리({자식: 부모})로 표현하는 게 직관적
• 트리를 타고 올라가며 10%씩 깎아 위로 전달하는 재귀적 분배 구조
• 1원 미만이면 분배 중단 → while과 if 두 곳에서 조건을 모두 체크해야 누락 없이 처리됨

---

✅ 최종 풀이 코드

def solution(enroll, referral, seller, amount):
    answer = []
    nodes = {c: {"parent": p, "price": 0} for c, p in zip(enroll, referral)}

    for s, a in zip(seller, amount):
        nodes[s]["price"] += a * 100
        current = s
        earn = a * 100 // 10

        while nodes[current]["parent"] != "-":
            p = nodes[current]["parent"]
            if earn < 1:
                break
            nodes[current]["price"] -= earn
            nodes[p]["price"] += earn
            current = p
            earn = earn // 10

        if earn >= 1:
            nodes[current]["price"] -= earn

    for c in enroll:
        answer.append(nodes[c]["price"])

    return answer

---

📊 복잡도 분석

구분 복잡도 근거

시간 복잡도	O(N * H)	N = seller 수, H = 트리 높이(최악의 경우 N)
공간 복잡도	O(N)	nodes 딕셔너리가 가입자 수 N에 비례

enroll 길이가 최대 10,000이지만, 10%씩 깎이는 금액이 빠르게 1원 미만이 되므로 실제 while 루프 반복 횟수는 매우 적다.

---

❌ 오답 노트

시도 틀린 이유 수정 내용

1차	current = dict[p]['parent']로 한 단계를 건너뜀 → 중간 노드 분배 누락	current = p로 수정하여 정확히 한 칸씩만 이동
2차	최상위 직속 판매원의 10% 차감이 빠짐 (while 조건 때문에 루프 진입 자체가 안 됨)	루프 종료 후 if earn >= 1: nodes[current]['price'] -= earn 추가
3차	earn == 1일 때 earn > 1 조건이라 차감이 누락됨	earn >= 1로 경계값 수정
4차	통과 ✅	-

---

🔄 다른 풀이 방법

재귀로 구현하기

def solution(enroll, referral, seller, amount):
    parent = {c: p for c, p in zip(enroll, referral)}
    price = {c: 0 for c in enroll}

    def distribute(name, earn):
        if name == "-" or earn < 1:
            return
        share = earn // 10
        price[name] -= share
        p = parent[name]
        if p != "-":
            price[p] += share
            distribute(p, share)

    for s, a in zip(seller, amount):
        price[s] += a * 100
        distribute(s, a * 100 // 10)

    return [price[c] for c in enroll]

반복문 vs 재귀 비교:

• 반복문(while): 명시적으로 흐름이 보여 디버깅이 쉬움, 변수 추적이 직관적
• 재귀: 코드가 짧아지지만 "지금 어디까지 왔는지" 추적이 한눈에 안 들어옴
• 이 문제는 트리 높이가 깊지 않아 재귀 호출 스택 부담은 거의 없음

---

📝 배운 점 & 회고

• ✏️ 새로 알게 된 것: 자식 → 부모 방향으로만 탐색해야 하는 트리는 굳이 클래스로 만들 필요 없이 딕셔너리({자식: 부모})만으로도 충분히 표현 가능하다.
• ✏️ 새로 알게 된 것: while 조건만으로 경계 처리를 다 끝냈다고 착각하기 쉽다. 루프를 빠져나온 직후의 상태(최상위 노드)도 별도로 처리해야 하는 경우가 있다.
• ⚠️ 실수했던 점: current = dict[p]['parent']처럼 한 단계를 무심코 건너뛰는 실수를 했다. "지금 처리해야 할 노드가 누구인지"를 매 줄마다 명확히 짚고 넘어가야 한다.
• ⚠️ 실수했던 점: 경계값(earn == 1)을 처음엔 놓쳤다. 부등호(> vs >=)는 항상 예제 입출력으로 직접 검증하는 습관이 필요하다.
• 💬 한 줄 요약: 자식이 부모를 아는 트리는 딕셔너리로 충분하다. while 루프를 빠져나온 뒤의 마지막 처리까지 챙기자!