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

문제

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

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

풀이

1. 서로소 집합 자료 구조 (Disjoint-set data structure)

tree 구조이므로 서로소 집합 자료 구조 (Disjoint-set data structure) 또는 Union-Find 알고리즘을 응용하여 사용한다.

2. 시간초과

case11, csae12, case13에서 시간초과가 발생했다. 남은 이익이 0이 될때 탐색을 멈추도록 하면 해결할 수 있었다. (다른 사람의 풀이를 보고 확인했다...)

시간초과 코드

def solution(enroll, referral, seller, amount):
    parent = {c:p for c, p in zip(enroll, referral)} # 부모정보를 저장
    ans = {c:0 for c in enroll} # 각 노드별 이익을 저장
    
    for s, m in zip(seller, amount) : 
        m*=100 # 칫솔 한개당 100원
        
        while s in parent :
            ans[s] += m-int(m*0.1) # 노드에 이익저장하기
            m = int(m*0.1) # 남은 금액 저장하기
            s = parent[s] # 노드 갱신하기
    
    return [ans[c] for c in enroll] # enroll 순서대로 이익금 리스트 만들기

코드

def solution(enroll, referral, seller, amount):
    parent = {c:p for c, p in zip(enroll, referral)} # 부모정보를 저장
    ans = {c:0 for c in enroll} # 각 노드별 이익을 저장
    
    for s, m in zip(seller, amount) : 
        m*=100 # 칫솔 한개당 100원
        
        while s in parent and m>0 :
            ans[s] += m-int(m*0.1) # 노드에 이익저장하기
            m = int(m*0.1) # 남은 금액 저장하기
            s = parent[s] # 노드 갱신하기
    
    return [ans[c] for c in enroll] # enroll 순서대로 이익금 리스트 만들기