https://school.programmers.co.kr/learn/courses/30/lessons/77486

다단계에서 칫솔 판매하는데 상급자에게 수익의 10%를 반올림한 것을 바쳐야하는 구조이다. 판매 실적이 주어질 때 수익이 어떻게 되는지 찾는 문제이다.

Python

1차 시도 - 실패

def solution(enroll, referral, seller, amount):
    answer = []
    
    tree = dict()
    rev = dict()
    sell = dict()
    level = dict()
    for e in enroll:
        tree[e] = list()
        rev[e] = 0
        sell[e] = 0
        level[e] = 0
    
    for idx, r in enumerate(referral):
        if r != "-":
            tree[r].append(enroll[idx])
    
    for idx, s in enumerate(seller):
        sell[s] = amount[idx] * 100
    

    # root 찾기
    for e in enroll:
        que = [(e, 0)]
        idx = 0
        while idx < len(que):
            now, lev = que[idx]
            idx += 1
            for next in tree[now]:
                que.append((next, lev+1))
        for q, l in que:
            level[q] = max(level[q], l)
    tree["center"] = []
    rev["center"] = sell["center"] = 0
    
    for e, l in level.items():
        if l == 0:
            tree["center"].append(e)
            
    def dfs(now):    
        cost = [sell[now]]
        
        for next in tree[now]:
            cost += dfs(next)
        s = 0
        for idx, c in enumerate(cost):
            s += c - int(c / 10)
            cost[idx] = int(c / 10)
        
        rev[now] = s
        
        return cost
    dfs("center")
    for e in enroll:
        answer.append(rev[e])
    
    return answer

DFS로 수익을 계산하는 것이 낫겠다 판단했다. 탐색하면서 하급자들이 얻은 수익을 cost라는 리스트에 추가해주었다.
모든 하급자 탐색이 끝나면 cost를 돌면서 10%의 수익을 뗀 나머지를 s에 더하고 cost에는 10%의 수익을 저장했다.
결과적으로 본인은 s만큼의 수익을 얻게되고 rev에 저장한 후, 상급자에게 cost를 반환해준다.

이렇게 하기 위해서 root를 찾을 필요가 있었다. input에는 root가 주어지지 않았기에 bfs를 통해서 각 사람의 level을 측정하고, 모든 탐색이 끝난 후 level이 0인 사람을 추려서 root의 자식으로 넣어주었다.

문제에 주어진 테스트케이스는 통과하였는데 제출하니까 실패했다. 심지어 마지막 3개의 테스트 케이스는 런타임 에러가 발생하기도 했다.

2차 시도

def solution(enroll, referral, seller, amount):
    rev = [0] * len(enroll)
    
    enum = dict()
    for i, e in enumerate(enroll):
        enum[e] = i
    
    for idx, s in enumerate(seller):
        money = amount[idx] * 100
        while s != "-" and money > 0:
            i = enum[s]
            rev[i] += money - money//10
            money //= 10
            s = referral[i]
    
    return rev

다른 풀이를 참고해서 해결했다. 트리 모양만 보고 너무 복잡하게 접근했던 것 같다.
enroll의 index를 따로 저장해줄 딕셔너리를 만들어줬다. 그리고 seller를 돌면서 해당 seller의 판매금을 구해서 money에 저장해주었다.

while문을 통해서 상급자에게 떼줄 10%를 제한 나머지를 본인의 수익인 rev에 더해주었고, 상급자에게 떼줄 10%를 money에 저장한 뒤 referral에서 상급자를 찾았다.

순간 상급자가 없는 referral이 "-"인 사람일 때 money는 어떻게 되지라고 고민했으나 center에 수익이 몰리기에 상관이 없다는 것을 깨달았다.

tree를 본다고 무조건 평소에 쓰던 bfs, dfs 혹은 다익스트라나 기타 등등의 알고리즘이 정답이라는 생각은 버려야겠다.