[python] 프로그래머스 - 다단계 칫솔 판매(2021 Dev-Matching: 웹 백엔드 개발자(상반기))

🤔문제 해결

1. 판매원을 키, 추천인과 수익을 밸류로 하는 딕셔너리를 만든다. (enroll, referral)
   

   

2. 칫솔을 판매한 사람을 선택하고, 추천인과 수익을 계속 나눈다.

 

💨 보통 이렇게 하면 마지막 3개의 케이스에서 시간초과가 발생한다.

그 이유는 수익을 더 이상 나눌 수 없는 상태여도 추천인을 따라서 0원의 수익을 나눠 갖는 척을 하기 때문

따라서 더 이상 수익을 나눌 수 없는 상황이 되면 반복문을 멈춰준다.

 

💻소스 코드

 def solution(enroll, referral, seller, amount):
    answer = []
    multistages = {'-': ['', 0]}

    for e, r in zip(enroll, referral):
        multistages[e] = [r, 0]

    for s, a in zip(seller, amount):
        a *= 100
        while s != '-':  # '-': 민호, 민호 만나면 그만
            if a == 0:  # 수익이 0원이어도 계속 추천인과 분배를 하기 때문에 시간적 효율을 위해 그만
                break

            multistages[s][1] += a - a // 10
            a //= 10

            s = multistages[s][0]

    for e in enroll:
        answer.append(multistages[e][1])

    return answer


solution(
    ["john", "mary", "edward", "sam", "emily", "jaimie", "tod", "young"],
    ["-", "-", "mary", "edward", "mary", "mary", "jaimie", "edward"],
    ["young", "john", "tod", "emily", "mary"],
    [12, 4, 2, 5, 10]
)

 

📕문제 확인

출처: 프로그래머스