[프로그래머스]다단계 칫솔 판매

[29] 다단계 칫솔 판매

책 구매하기

문제 정보

• 분류: 트리
• 정답률: 39%
• 권장 시간 복잡도: O(S * H)
• 핵심 키워드: 트리, 부모 포인터, 수익 분배, 반복 전파
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/77486

문제를 읽을 때 체크할 포인트

판매 수익이 부모 방향으로 10%씩 올라가는 구조만 정확히 구현하면 된다. 각 사람의 추천인을 부모 포인터로 저장하고, 판매가 생길 때마다 위로 타고 올라가며 금액을 나누면 된다.

이 문제는 트리 전체를 순회하는 문제가 아니라, 판매가 일어났을 때 현재 사람에서 추천인 방향으로 이익을 올려 보내는 문제이다. 한 단계 올라갈 때마다 금액이 줄어들고 0원이 되면 더 볼 필요가 없다는 점까지 같이 챙겨야 한다.

풀이 흐름

1. 이름을 인덱스로 바꾸고 추천인 부모 배열을 만든다.
2. 판매 기록을 하나씩 보며 현재 사람의 수익을 계산한다.
3. 10%를 부모에게 넘기고 90%를 본인에게 더하는 과정을 루트까지 반복한다.

구현할 때 놓치기 쉬운 부분

이익을 추천인 방향으로 올릴 때 10%를 정수 나눗셈으로 처리해야 한다. 부모에게 넘길 금액과 현재 판매자가 남길 금액을 한 번에 정리하지 못하면 값이 쉽게 꼬인다.

파이썬 정답 코드

def solution(enroll, referral, seller, amount):
  # 이름을 인덱스로 바꾸고 추천인 부모 배열을 만든다.
  index = {name: i for i, name in enumerate(enroll)}
  parent = [-1] * len(enroll)

  # 판매 기록을 하나씩 보며 현재 사람의 수익을 계산한다.
  for i, ref in enumerate(referral):
    if ref != "-":
      parent[i] = index[ref]

  profit = [0] * len(enroll)

  # 10%를 부모에게 넘기고 90%를 본인에게 더하는 과정을 루트까지 반복한다.
  for name, cnt in zip(seller, amount):
    money = cnt * 100
    cur = index[name]

    while cur != -1 and money > 0:
      share = money // 10
      profit[cur] += money - share
      cur = parent[cur]
      money = share

  return profit

시간 복잡도

S는 판매 기록 수이고, H는 추천 트리의 높이이다.

판매 기록이 S건이면 기록 하나마다 추천인 체인을 타고 위로 올라가는 작업이 붙는다. 한 건이 위로 올라가는 최대 길이를 트리 높이 H로 두면 전체는 O(S * H)이다.

따라서 시간 복잡도는 O(S * H)이다.