프로그래머스 LV3 - 다단계 칫솔 판매

문제 링크

내 풀이

# 자신이 받은 금액의 10%를 자신의 추천인에게 분배(받을 때마다)
# 자신이 가입시킨 추천인들에게 개개인 판매수익 10%씩 받음
# 10% 금액 >= 1 일 경우에만 추천인에게 분배, 미만이면 본인이 가짐

# 재귀로 호출해서 판매금액을 계속 더해가는 식으로 전개
import math

def solution(enroll, referral, seller, amount):  
    def div_money(name,money):
        if name == '-':
            return money_dict
        money_dict[name] += math.ceil(money * 0.9)
        if money * 0.1 < 1:
            return money_dict
        else:
            money = math.floor(money * 0.1)
            div_money(referral_dict[name], money)
    money_dict = {}
    referral_dict = {}
    answer = []
    for man in enroll:
        money_dict[man] = 0
    for man, ref_man in zip(enroll,referral):
        referral_dict[man] = ref_man
    for sell_man, toothbrush in zip(seller, amount):
        money = toothbrush * 100
        div_money(sell_man, money)
    for man in enroll:
        answer.append(money_dict[man])
        
    return answer

다른 풀이

def solution(enroll, referral, seller, amount):
    parent = dict(zip(enroll, referral))

    total = {name: 0 for name in enroll}

    for i in range(len(seller)):
        money = amount[i] * 100
        cur_name = seller[i]
        while money > 0 and cur_name != '-':
            total[cur_name] += money - money // 10
            cur_name = parent[cur_name]
            money //= 10
    
    return [total[name] for name in enroll]
    
    출처 : 코딩테스트 합격자 되기 파이썬 편, 저자: 박경록

풀이 해석

• enroll, referral의 노드를 활용하여 dict를 만들고
• 이름과 수익금을 저장할 dict도 초기화를 해준다
• cur_name, money를 최신화해가며 while 문을 돌리고 특정 조건이 불만족되면 while 문을 종료한다

배울 점

• dict(zip(enroll, referral))로 바로 dict 만들기
• {name: 0 for name in enroll}로 바로 초기화
• [total[name] for name in enroll] 리스트 컴프리핸션

시간복잡도 비교

• 내풀이

테스트 1 〉	통과 (0.03ms, 10.3MB)
테스트 2 〉	통과 (0.16ms, 10.2MB)
테스트 3 〉	통과 (0.06ms, 10.2MB)
테스트 4 〉	통과 (0.24ms, 10.1MB)
테스트 5 〉	통과 (2.00ms, 10.5MB)
테스트 6 〉	통과 (4.13ms, 13MB)
테스트 7 〉	통과 (3.42ms, 13MB)
테스트 8 〉	통과 (5.06ms, 13.1MB)
테스트 9 〉	통과 (26.07ms, 14MB)
테스트 10 〉	통과 (244.84ms, 21.1MB)
테스트 11 〉	통과 (222.58ms, 20.5MB)
테스트 12 〉	통과 (234.95ms, 20.5MB)
테스트 13 〉	통과 (245.70ms, 20.5MB)

• 다른 풀이

  테스트 1 〉	통과 (0.02ms, 10.1MB)
  테스트 2 〉	통과 (0.12ms, 10.1MB)
  테스트 3 〉	통과 (0.04ms, 10.3MB)
  테스트 4 〉	통과 (0.12ms, 10.3MB)
  테스트 5 〉	통과 (0.84ms, 10.2MB)
  테스트 6 〉	통과 (2.24ms, 12.5MB)
  테스트 7 〉	통과 (2.30ms, 12.4MB)
  테스트 8 〉	통과 (3.32ms, 12.4MB)
  테스트 9 〉	통과 (13.57ms, 13.3MB)
  테스트 10 〉	통과 (115.26ms, 20.9MB)
  테스트 11 〉	통과 (97.73ms, 20.4MB)
  테스트 12 〉	통과 (95.16ms, 20.5MB)
  테스트 13 〉	통과 (120.33ms, 20.5MB)