문제 요약
다단계 판매 조직에서 판매원이 칫솔을 판매하면 판매 이익의 10%를 추천인에게 전달하고, 나머지는 자신이 가진다.
추천인도 전달받은 금액의 10%를 자신의 추천인에게 전달한다. 전달할 금액이 1원 미만이면 더 이상 분배하지 않고 현재 판매원이 전부 가진다.
모든 판매 기록을 처리한 뒤 enroll 순서에 맞춰 각 판매원의 최종 이익을 반환해야 한다.
핵심 아이디어
각 판매원은 추천인을 한 명만 가지므로 조직 구조는 부모 방향으로만 이동하는 트리다.
판매 기록 하나가 들어오면 다음 과정을 반복한다.
- 현재 판매 이익의 10%를 계산한다.
- 10%를 제외한 금액을 현재 판매원의 이익에 더한다.
- 10% 금액을 추천인에게 전달한다.
- 추천인이 없거나 전달 금액이 0이면 종료한다.
조직 전체를 순회할 필요 없이, 판매원에서 센터 방향으로 이어지는 부모 경로만 확인하면 된다.
이름을 인덱스로 변환하기
문자열 이름으로 추천인을 반복 탐색하면 불편하므로 판매원의 이름을 enroll 인덱스로 변환한다.
name_to_index = {name: index for index, name in enumerate(enroll)}parent[index]에는 해당 판매원의 추천인 인덱스를 저장한다.
- 추천인이
"-"이면 센터가 추천인이므로-1을 저장한다. - 추천인이 판매원 이름이면 그 판매원의 인덱스를 저장한다.
parent = [
-1 if referrer == "-" else name_to_index[referrer]
for referrer in referral
]이제 부모 찾기와 이익 누적을 배열로 처리할 수 있다.
이익 분배 규칙
현재 전달해야 하는 금액을 profit이라고 하자.
commission = profit // 10
earnings[current] += profit - commissionprofit // 10은 원 단위 절사를 자연스럽게 처리한다.
예를 들어 profit이 19원이면 추천인에게 전달하는 금액은 1원이고 현재 판매원은 18원을 가진다.
profit이 9원이면 추천인에게 전달하는 금액은 0원이므로 현재 판매원이 9원 전체를 가진 뒤 분배를 끝낸다.
Python 코드
def solution(enroll, referral, seller, amount):
name_to_index = {
name: index
for index, name in enumerate(enroll)
}
parent = [
-1 if referrer == "-" else name_to_index[referrer]
for referrer in referral
]
earnings = [0] * len(enroll)
for seller_name, sold_count in zip(seller, amount):
current = name_to_index[seller_name]
profit = sold_count * 100
while current != -1 and profit > 0:
commission = profit // 10
earnings[current] += profit - commission
current = parent[current]
profit = commission
return earnings코드 설명
부모 배열 생성
parent = [
-1 if referrer == "-" else name_to_index[referrer]
for referrer in referral
]센터는 enroll에 포함되지 않는다. 따라서 센터에 도달한 상태는 -1로 표현한다.
current == -1이 되면 센터로 전달할 금액까지 계산이 끝난 것이므로 반복을 종료한다. 센터가 받은 수익은 반환 대상이 아니다.
판매 이익 계산
profit = sold_count * 100칫솔 한 개의 이익은 100원이므로 판매량에 100을 곱해 최초 이익을 구한다.
추천인 방향으로 분배
while current != -1 and profit > 0:
commission = profit // 10
earnings[current] += profit - commission
current = parent[current]
profit = commission현재 판매원이 자신이 가질 금액을 먼저 누적한 뒤, 추천인으로 이동하면서 전달할 금액만 다음 profit으로 사용한다.
전달 금액이 0이 되면 더 이상 이익이 위로 전달되지 않으므로 반복을 종료한다.
정확성
각 판매 기록에 대해 알고리즘은 현재 판매 이익의 10%를 profit // 10으로 계산한다. 이는 문제의 원 단위 절사 규칙과 같다.
현재 판매원에게는 profit - commission을 누적하므로, 현재 이익에서 추천인에게 전달할 금액을 제외한 나머지를 정확히 가진다.
이후 추천인을 현재 위치로, 전달 금액을 다음 이익으로 설정하므로 같은 규칙이 센터 방향의 모든 추천인에게 순서대로 적용된다.
전달 금액이 0이면 현재 판매원이 남은 이익 전체를 가지며 더 전달할 이익이 없다. 센터에 도달하면 반환 대상 판매원이 없으므로 분배를 종료한다.
따라서 모든 판매 기록을 처리한 뒤 earnings[i]에는 enroll[i] 판매원이 얻은 이익의 총합이 정확히 저장된다.
시간 복잡도
판매 기록 수를 S, 한 판매 기록에서 추천인을 따라 올라가는 횟수를 H라고 하자.
각 판매 기록은 부모 방향으로 최대 H번 이동하므로 시간 복잡도는 다음과 같다.
O(S × H)하지만 전달 금액은 매 단계 10분의 1로 감소한다. 이익이 0이 되면 즉시 반복이 끝나므로 실제 반복 횟수는 매우 작다.
공간 복잡도
이름-인덱스 딕셔너리, 부모 배열, 이익 배열을 사용한다.
판매원 수를 N이라고 하면 공간 복잡도는 다음과 같다.
O(N)주의할 점
- 10%는 반올림이 아니라 원 단위 절사이므로
profit // 10을 사용해야 한다. - 추천인이 센터인 경우
"-"로 주어지며, 센터의 이익은 반환 배열에 포함하지 않는다. - 같은 판매원이 여러 번 판매할 수 있으므로 기존 이익에 누적해야 한다.
- 전달 금액이
0이면 더 이상 부모 방향으로 이동할 필요가 없다. seller와amount는 같은 순서의 판매 기록이므로zip()으로 함께 순회한다.
정리
이 문제는 복잡한 그래프 탐색보다 부모 방향 이익 전달을 정확히 구현하는 시뮬레이션 문제다.
이름을 인덱스로 변환하고, 각 판매 건마다 현재 이익 // 10을 추천인에게 전달하는 과정을 반복하면 간결하게 해결할 수 있다.
