[프로그래머스] 다단계 칫솔 판매 - PYTHON

문제보기

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

프로그래머스

 

 

 

 

풀미 & 코드

해당 문제는 별다른 알고리즘 활용이나 번뜩이는 인사이트 보다 단지 러닝타임을 줄이는 문제라고 생각된다. (마지막 케이스인 11, 12, 13이 최대 관문이다) 사용된 알고리즘은 문제 설명에서와 같이 sellers를 돌면서 root까지 해당하는 노드의 부모 노드를 방문해 amount를 계산하였다.

 

 

 

필자는 러닝타임을 줄이기 위해 name_idx라는 dictionary을 사용했다. 만약 dict를 사용하지 않는다면, 파라미터 sellers의 원소인 seller에 맞는 enroll을 가져오기 위해서 다음과 같은 방식을 사용해야 한다.

idx = enroll.index(seller)

하지만 index 매서드를 사용한 방식은 O(n)의 시간 복잡도가 필요하다. 따라서 enroll이 커질수록 러닝타임 또한 매우 커지기 때문에 시간 복잡도 O(1)인 dict를 사용해 다음과 같은 방식으로 바꾸었다.

idx = name_idx(seller)

 

 

 

전체 풀이 코드는 다음과 같다!

def solution(enroll, referral, sellers, amounts):
    result = [0 for _ in range(len(enroll))]
    name_idx = {}
    
    for i, name in enumerate(enroll):
        name_idx[name] = i
        
    for i, seller in enumerate(sellers):
        amount = amounts[i] * 100
        while seller != "-" and amount != 0:
            idx = name_idx[seller]
            next_amount = amount // 10 
            result[idx] += amount - next_amount
            
            seller = referral[idx]
            amount = next_amount
        
    return result

 

 

 

회고

 

사실 필자는 처음에 다른 방식으로 코드를 작성했다. 위의 방식처럼 한번에 한 seller씩 amount를 계산하면(while문을 사용해 seller의 parent node를 계속해 방문하면서 amount를 계산하는 방식), 한 노드를 여러번 방문하기 때문에 비효율적이라고 생각했다. 따라서 sellers를 돌면서 dict에 노드별로 금액들을 리스트화해서 저장했고, enroll을 역방향으로 돌면서 바로 위의 부모에만 amount을 계산에 넣었다.

 

def solution(enroll, referral, sellers, amounts):
    n = len(enroll)
    result = [0 for _ in range(n)]
    sub_amounts = {}
    
    # amount를 계산해야 하는 노드들만 sub_amounts에 추가
    for i, seller in enumerate(sellers):
        amount = amounts[i] * 100
        sub_amounts[seller] = sub_amounts.get(seller, []) + [amount]
    
    # leaf부터 노드를 방문하며 만일 amount가 있다면 계산
    for i in reversed(range(n)):
        seller = enroll[i]
        if seller not in sub_amounts.keys():
            continue
        
        for amount in sub_amounts[seller]:
            next_amount = amount // 10
            result[i] += (amount - next_amount)
            
            next_seller = referral[i]
            if next_seller != "-" and next_amount != 0:
                sub_amounts[next_seller] = sub_amounts.get(next_seller, []) + [next_amount]
        
    return result

 

하지만 이런 방식으로 풀게 된다면 테스트케이스 11, 12, 13에서 시간 초과가 발생한다... 필자의 생각에는 범위의 차이라고 생각된다. enroll의 길이는 1 이상 10,000 이하이며 seller의 길이는 1 이상 100,000 이하이다. 즉 seller의 길이가 10배 더 크다! 후기에 쓰인 알고리즘으로 푼다면 enroll 의 길이 * 노드에 포함된 sellers의 개수만큼 시간 복잡도가 수행된다. seller의 길이가 enroll보다 크기 때문에 노드에 포함된 sellers의 개수이 클것으로 예상된다. 반대로 풀이&코드 알고리즘의 시간복잡도는 sellers의 길이 * 수행되는 깊이(최대 4)이기 때문에 상대적으로 적을 것으로 예상된다..ㅎ