Level 3 다단계 칫솔 판매 Python 3

https://programmers.co.kr/learn/courses/30/lessons/77486?language=python3 

코딩테스트 연습 - 다단계 칫솔 판매

 

최종 코드

• GitHub -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_다단계칫솔판매.py

hwayeon351/Programmers-Algorithms

def solution(enroll, referral, seller, amount):
    levels = dict()
    earns = dict()
    for e, r in zip(enroll, referral):
        levels[e] = r
        earns[e] = 0
    for s, a in zip(seller, amount):
        e = a*100
        refer = levels[s]
        while refer != '-':
            fee = e//10
            earns[s] += (e-fee)
            e = fee
            s = refer
            refer = levels[s]
            if e == 0: break
        else: earns[s] += (e-e//10)
    return list(earns.values())

---

풀이 과정

풀이 시간 34분

트리 구조인 다단계 조직도를 levels 딕셔너리로 표현하였다. 이 때, key 값은 판매원이고 value는 해당 판매원을 추천한 추천인을 담아주었다.

seller 리스트 항목을 순서대로 탐색하면서 levels 딕셔너리를 통해 계속해서 추천인들을 탐색하며 이익을 계산해주고 추천인이 '-'인 경우 탐색을 종료하도록 하여 문제를 해결하였다.

def solution(enroll, referral, seller, amount):
	#key = 판매원, value = key를 추천한 추천인
    levels = dict()
    #key = 판매원, value = key의 이익
    earns = dict()
    #딕셔너리 초기화
    for e, r in zip(enroll, referral):
        levels[e] = r
        earns[e] = 0
    #이익 계산
    for s, a in zip(seller, amount):
    	#판매 수익 e과 s의 추천인 refer
        e = a*100
        refer = levels[s]
        #추천인이 '-'일 때까지 조직도를 탐색하여 이익 계산
        while refer != '-':
        	#추천인에게 줘야 할 이익금의 10%인 fee를 뺀 나머지를 판매원의 수익에 더함
            fee = e//10
            earns[s] += (e-fee)
            #다음 추천인을 탐색하기 위해 e, s, refer을 바꿔줌
            e = fee
            s = refer
            refer = levels[s]
            #만약 e가 0인 경우 추천인에게 나눠 줄 이익이 없으므로 반복 종료
            if e == 0: break
        #while문이 break에 걸리지 않고 종료되는 경우 실행
        #추천인이 center인 경우, 이익의 10%를 뺀 나머지를 판매원 수익에 더함
        else: earns[s] += (e-e//10)
    return list(earns.values())
    #시간복잡도 = O(nlogn), 공간복잡도 = O(n)

시간복잡도는 이익 계산을 해주는 알고리즘에서 seller의 길이만큼 바깥 for문이 반복되고 O(n), root 노드에 도달 할 때까지 while문이 해당 추천인의 트리 레벨만큼 발생한다.O(logn)

따라서, 시간복잡도는 O(nlogn)이며, 공간복잡도는 2개의 딕셔너리가 사용되고 각 key마다 value 값이 하나이기 때문에 O(n)이다.