[Coding Test][Python][프로그래머스] Level 3 다단계 칫솔 판매

Lv.3 다단계 칫솔 판매

문제)

민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, 조직을 운영하던 민호는 조직 내 누가 얼마만큼의 이득을 가져갔는지가 궁금해졌습니다. 예를 들어, 민호가 운영하고 있는 다단계 칫솔 판매 조직이 아래 그림과 같다고 합시다.

민호는 center이며, 파란색 네모는 여덟 명의 판매원을 표시한 것입니다. 각각은 자신을 조직에 참여시킨 추천인에 연결되어 피라미드 식의 구조를 이루고 있습니다. 조직의 이익 분배 규칙은 간단합니다.

모든 판매원은 칫솔의 판매에 의하여 발생하는 이익에서 10% 를 계산하여 자신을 조직에 참여시킨 추천인에게 배분하고 나머지는 자신이 가집니다.

모든 판매원은 자신이 칫솔 판매에서 발생한 이익 뿐만 아니라, 자신이 조직에 추천하여 가입시킨 판매원에게서 발생하는 이익의 10% 까지 자신에 이익이 됩니다.

자신에게 발생하는 이익 또한 마찬가지의 규칙으로 자신의 추천인에게 분배됩니다. 단, 10% 를 계산할 때에는 원 단위에서 절사하며, 10%를 계산한 금액이 1 원 미만인 경우에는 이득을 분배하지 않고 자신이 모두 가집니다.

예를 들어, 아래와 같은 판매 기록이 있다고 가정하겠습니다. 칫솔의 판매에서 발생하는 이익은 개당 100 원으로 정해져 있습니다.

판매원	판매수량	이익금
young	12	1200원
john	4	400원
tod	2	200원
emily	5	500원
mary	10	1000원

판매원 young 에 의하여 1,200 원의 이익이 발생했습니다. young 은 이 중 10% 에 해당하는 120 원을, 자신을 조직에 참여시킨 추천인인 edward 에게 배분하고 자신은 나머지인 1,080 원을 가집니다.

edward 는 young 에게서 받은 120 원 중 10% 인 12 원을 mary 에게 배분하고 자신은 나머지인 108 원을 가집니다. 12 원을 edward 로부터 받은 mary 는 10% 인 1 원을 센터에 (즉, 민호에게) 배분하고 자신은 나머지인 11 원을 가집니다. 이 상태를 그림으로 나타내면 아래와 같습니다.

 

각 판매원의 이름을 담은 배열 enroll,

각 판매원을 다단계 조직에 참여시킨 다른 판매원의 이름을 담은 배열 referral,

판매량 집계 데이터의 판매원 이름을 나열한 배열 seller,

판매량 집계 데이터의 판매 수량을 나열한 배열 amount가 매개변수로 주어질 때,

각 판매원이 득한 이익금을 나열한 배열을 return 하도록 solution 함수를 완성해주세요. 판매원에게 배분된 이익금의 총합을 계산하여(정수형으로), 입력으로 주어진 enroll에 이름이 포함된 순서에 따라 나열하면 됩니다.

제한 사항

• enroll의 길이는 1 이상 10,000 이하입니다.
  • enroll에 민호의 이름은 없습니다. 따라서 enroll의 길이는 민호를 제외한 조직 구성원의 총 수입니다.
• referral의 길이는 enroll의 길이와 같습니다.
  • referral 내에서 i 번째에 있는 이름은 배열 enroll 내에서 i 번째에 있는 판매원을 조직에 참여시킨 사람의 이름입니다.
  • 어느 누구의 추천도 없이 조직에 참여한 사람에 대해서는 referral 배열 내에 추천인의 이름이 기입되지 않고 “-“ 가 기입됩니다. 위 예제에서는 john 과 mary 가 이러한 예에 해당합니다.
  • enroll 에 등장하는 이름은 조직에 참여한 순서에 따릅니다.
  • 즉, 어느 판매원의 이름이 enroll 의 i 번째에 등장한다면, 이 판매원을 조직에 참여시킨 사람의 이름, 즉 referral 의 i 번째 원소는 이미 배열 enroll 의 j 번째 (j < i) 에 등장했음이 보장됩니다.
• seller의 길이는 1 이상 100,000 이하입니다.
  • seller 내의 i 번째에 있는 이름은 i 번째 판매 집계 데이터가 어느 판매원에 의한 것인지를 나타냅니다.
  • seller 에는 같은 이름이 중복해서 들어있을 수 있습니다.
• amount의 길이는 seller의 길이와 같습니다.
  • amount 내의 i 번째에 있는 수는 i 번째 판매 집계 데이터의 판매량을 나타냅니다.
  • 판매량의 범위, 즉 amount 의 원소들의 범위는 1 이상 100 이하인 자연수입니다.
• 칫솔 한 개를 판매하여 얻어지는 이익은 100 원으로 정해져 있습니다.
• 모든 조직 구성원들의 이름은 10 글자 이내의 영문 알파벳 소문자들로만 이루어져 있습니다

---

풀이)

※ 풀이 아이디어

1. 처음에 Tree와 DFS를 통해 Path를 구하고 이를 바탕으로 이익을 계산하려 하였다
2. 하지만, 아래에서부터 올라오기 때문에 Union - Find 구조에서 Find를 사용하여 parent를 찾아가며 이익을 계산하여 해결할 수 있다.
(처음에 Find 알고리즘로 Path를 구해 이익금을 분배하였는데, 런타임 에러 및 시간초과가 발생했다. 이와 같은 상황이신 분들은 정답 코드 아래 오류 코드 있으니 참고하시면 됩니다)

 

아래 풀이처럼 Find 알고리즘을 조금 수정하여 parent로 올라가며 이익금 분배에 대해 계산하였다.

curr_price가 0이 되면 더이상 올라갈 필요가 없기 때문에 재귀함수를 종료한다.

import sys
sys.setrecursionlimit(10 ** 6)
def distribute(parent, x, curr_price, res):
	# 더이상 올라갈 필요 없음
    if curr_price == 0:
        return
    
    if x == "-":
        return
    else:
        remain = int(curr_price * 0.1)
        res[x] += (curr_price-remain)
        curr_price = remain
        # curr을 parent로 올라가서 이익금 계산
        distribute(parent, parent[x], curr_price, res)
        
def solution(enrolls, referrals, sellers, amounts):
    answer = []
    N = len(enrolls)
    parent = {}
    res = {}
    for enroll, ref in zip(enrolls, referrals):
        parent[enroll] = ref
        res[enroll] = 0
    
    for seller, amount in zip(sellers, amounts):
        # seller가 100 * amount의 이익을 냈고 parent를 따라 가면서 이익 계산
        total = 100 * amount
        distribute(parent, seller, total, res)
            
    for enroll in enrolls:
        answer.append(res[enroll])
    
    return answer

처음에 아래와 같이 parent를 path를 구해서 적용시켰는데, TC 11, 12, 13에서 런타임에러가 났다.
enrolls와, referrals의 길이가 최대 10,000이라 Skewed Tree(편향 트리)가 만들어지면 recursion limit에 걸릴 수 있다 생각이 들어 resursionlimit을 10**6으로 늘려주었는데 시간초과가 났다.
그래서 정답 코드에서 curr_price == 0일 때, 즉 더 이상 배분할 이익금이 없을 때 재귀함수를 종료해 줄 필요가 있었다.

import sys
sys.setrecursionlimit(10 ** 6)
def find_parent(parent, x, path):
    if x == "-":
        return path
    else:
        path.append(x)
        return find_parent(parent, parent[x], path)

def solution(enrolls, referrals, sellers, amounts):
    answer = []
    N = len(enrolls)
    parent = {}
    res = {}
    for enroll, ref in zip(enrolls, referrals):
        parent[enroll] = ref
        res[enroll] = 0
    
    for seller, amount in zip(sellers, amounts):
        # seller가 100 * amount의 이익을 냈고 parent를 따라 가면서 이익 계산
        total = 100 * amount
        # 재귀 깊이 초과? -> 시간 초과
        # 즉, DFS로 시간 초과 발생
        path = find_parent(parent, seller, [])
        curr = total
        
        for p in path:
            remain = int(curr * 0.1)
            res[p] += (curr - remain)
            curr = remain
            
    for enroll in enrolls:
        answer.append(res[enroll])
    
    return answer