[Programmers] 다단계 칫솔 판매 in Python

문제 풀러가기!

전형적인 dfs 문제로 배열로 구분하는 것이 아닌 hash로 구분했습니다.

문제의 설명을 잘 보면 특정 노드부터 시작해서 해당 부모 노드로 타고타고 올라가는 방식이 가장 큰 특징이며, 문제에서 그렇게 정보를 주었기 때문에, 해당 데이터를 이용하여 특정 노드를 "key"을 두면서 그 key의 value값은 부모 노드로 지정해주면 됩니다. 이러면 이제 방문 여부를 체크해야 되지 않나요? 라는 생각이 들 수도 있지만, 그럴 필요도 없는게 부모 노드로 올라가기만 하기 때문에 단방향이며, 트리이기 때문에 순환이 존재하지 않습니다. 따라서 key와 value만 구성하여 dfs를 돌려도 충분히 가능합니다.

문제의 조건을 조금 더 파보겠습니다.

제한사항

• 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. 문제의 설명상 dfs를 활용한 재귀함수를 이용한 풀이가 적절해보입니다. 여기서 enroll 등록자가 10000명 이상이며 사용할 언어인 python의 경우 재귀 함수의 깊이는 1,000으로 default값으로 두고 있으니, 이것을 10,000까지 늘려줍시다.

2. referral의 길이는 enroll의 길이와 같기 때문에 이를 이용하여 등록자마다 다단계로 이끈 사람이 누군지 알 수 있습니다. 이 2개를 이용하여 enroll은 key값으로 referral은 value 값으로 활용할 수 있습니다.

3. "-"인 경우 value값을 "center"로 지정하면 됩니다. 물론 이끈 사람이 center라는 node가 존재한다면, 다르게 지정하는게 좋을 듯 합니다.

4. 100,000개의 데이터가 주어기지 때문에 단 한번의 순회로 문제를 풀어야 합니다. O(n^2)라면 시간초과일 확률이 높으며, hash table을 활용한 tree dfs 순회까지 더 해진다면 O(n)보다 더 높은 시간 복잡도를 갖을 것입니다. 문제의 조건에서 tree는 이진 트리는 아니기 때문에 아마 저 위의 시간보다 덜 걸릴 수 있으나, 최악의 경우 모든 부모가 한 자식만을 갖는다면, 10,000 ✖️ 100,000이 걸립니다. → ?????????

그러면 시간 초과나야되는거 아니야? 라고 생각하실 수 있지만, 문제에서 아주 후한 조건을 주었습니다. 따라서 10,000 * 100,000 순회는 절대 나올 수 없습니다. 6번에서 자세히 설명드리겠습니다.

5. amount는 개수를 나타내는 것이기 때문에 꼭 100을 곱한 형태로 넣어줍니다.

6. 모든 tree를 다 순회할 필요는 없습니다. 문제에서 0원이 되면, 더 이상 tree에 이득을 전해줄 이유가 없기 때문입니다. 사실 이부분 때문에, tree순회가 많이 줄어들긴 합니다. amount의 값은 최대 100이기 때문에 10,000까지가 최대이며, 10,000의 10%씩 전달해준다면, 4~5번의 dfs 깊이만 들어가도 이득이 1보다 작아지기 때문에 다음 깊이로 넘어가지 않아도 괜찮습니다. 따라서 제가 생각한 dfs를 활용한 풀이의 최대 시간 복잡도는 다음과 같습니다.

   $O(n * log(a) ), n=sellerSize, a=amountSize$

   이제 문제의 seller와 amount 정보를 받아 dfs를 순회하도록 만들면 끝입니다.

import sys
from collections import defaultdict

sys.setrecursionlimit(10**4)

def dfs(name, am):
    global benefit_dic, dadange

    if am == 0: return

    mine, recommend_people = am - int(am / 10), int(am / 10)
    benefit_dic[name] += mine

    for rec in dadange[name]: dfs(rec, recommend_people)


def solution(enroll, referral, seller, amount):
    global benefit_dic, dadange
    
    benefit_dic = defaultdict(int)
    dadange = defaultdict(list)

    benefit_dic["center"]
    dadange["center"]

    for en, re in zip(enroll, referral):
        if re != "-":
            dadange[en].append(re)
        else:
            dadange[en].append("center")
        benefit_dic[en]
        

    for sell, am in zip(seller, amount):
        dfs(sell, am*100)

    return [benefit_dic[i] for i in enroll]