사용자 도구

사이트 도구


ps:problems:programmers:77486

다단계 칫솔 판매

ps
링크programmers.co.kr/…
출처프로그래머스
문제 번호77486
문제명다단계 칫솔 판매
레벨Level 3
분류

트리

시간복잡도O(n+m)
인풋사이즈n<=10000, m<=100000
사용한 언어Python
해결날짜2021/07/06
출처

ps:problems:programmers:2021_dev-matching_-_웹_백엔드_개발자_상반기

풀이

  • 특별한 알고리즘 없이 그냥 그대로 구현하면 된다..
  • 자식이 업데이트될때 부모들도 똑같은 값이 증가된다면, 오일러 트리 테크닉과 세그먼트 트리를 이용하여 효율적으로 푸는 방법을 고민해 볼수 있겠지만, 이 문제는 그렇게 하기도 쉽지 않거니와 그렇게 할 필요도 없다. 이익이 최대 100*100 = 10000원이기 때문에, 10%씩 부모에게 떼어주는 것을 반복하면, 업데이트 되는 노드의 갯수는 최대 5개뿐이다. 따라서 한개의 쿼리에 5개 이하의 노드만 업데이트해주면 되므로 그냥 O(1)으로 생각할수 있다. n개의 노드로 트리를 만드는 데에는 O(n), m개의 쿼리를 각각 O(1)에 처리하는 데에는 O(m). 총 시간복잡도는 O(n+m).

코드

"""Solution code for "Programmers 77486. 다단계 칫솔 판매".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/77486
- Solution link: http://www.teferi.net/ps/problems/programmers/77486
"""

import collections

COST = 100


def solution(enroll, referral, seller, amount):
    parents = {child: parent for child, parent in zip(enroll, referral)}
    parents['-'] = '-'
    profits = collections.defaultdict(int)

    for s, a in zip(seller, amount):
        profit = a * COST
        member = s
        while profit > 0:
            profit_to_referral = profit // 10
            profits[member] += profit - profit_to_referral
            profit, member = profit_to_referral, parents[member]

    return [profits[x] for x in enroll]

토론

댓글을 입력하세요:
X L G W N
 
ps/problems/programmers/77486.txt · 마지막으로 수정됨: 2021/07/08 16:40 저자 teferi