[programmers] 다단계 칫솔 판매 python

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

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

 

 

1. 해결 방법

맨처음에는 재귀로 풀어보려고 했지만 테스트케이스는 다 통과 했지만 실제로 코드를 제출했을 때는 케이스 한개를 제외하곤 맞추지 못했다. 그 이유는 root로 부터 내려가면서 가장 끝 leaf에 도달했을 때 현재 가격을 90%로 만들고 10%를 반환하는 형태로 구현했다. 하지만 이런식으로 구현하면 자식 노드들의 값을 모두 더한 상태에서 10%를 부모 노드로 전달한다. 이 과정에서 문제가 발생한다.

 

조건에 따르면 특정 노드는 상위노드에게 10%씩 커미션을 내야하는데 루트에 가까워 질수록 커미션이 1/10로 줄어든다. 이런식으로 줄어들다가 커미션이 1이하가 되면 더 이상 커미션을 주지 않아도 된다. 하지만 현재 노드에 자식노드의 커미션 합을 진행 후 10%를 하게 되면 특정 조건에서는 더 상위에 있는 노드까지 커미션을 제출 하게 된다. 즉 커미션합을 한 후에 상위노드로 커미션을 주게되면 개별 자식 노드에서 커미션을 줄 때보다 더 많은 돈을 상위노드로 준다. 

 

따라서 이 문제는 하나의 노드에 대해서 해당 노드보다 상위에 있는 노드로 모두 커미션을 지불하는 방법으로 구현해야한다.

 

이 문제에 대한 풀이를 검색해보면 파이썬으로 푼 대부분의 문제가 11, 12, 13번 케이스에 대해 Time Out이 나오는 것을 볼 수 있는데

이는 단계가 올라가면서 커미션이 1이하가 되었을 때 멈추지 않고 모든 상위 노드에 대해 커미션을 지불하기 때문이다.

def solution(enroll, referral, seller, amount):
    N_enroll = len(enroll)
    
    #answer[i] : i번째 사람이 갖고 있는 돈
    answer = [0 for _ in range(N_enroll)]
    
    #index[name] : 이름이 name인 사람의 answer에서의 위치
    idex={index[name]=idx for idx,name in enumerate(enroll)}
    
    for idx, name in enumerate(seller):   
        price=100*amount[idx] # 칫솔 개수 * 100 
        answer[index[name]] += price
        
        #해당 사람의 refferal이 center(root)전까지
        while referral[index[name]]!="-":
        
        	#현재 사람이 번 돈에서 10%를 떼어서
            answer[index[name]]-=price//10
            
            #refferal에게 준다.
            name=referral[index[name]]
            answer[index[name]]+=price//10
            
            #한단계 올라가면서 커미션은 10% 감소
            price=price//10
            
            #커미션이 0이면 더이상 주지 않아도된다.
            if price==0:
                break
        
        #마지막사람(피라미드의 제일 위에 있는 사람)도 center에게 10% 떼어줘야한다. 
        answer[index[name]]-=price//10
    return answer