[Programmers] 다단계 칫솔 판매

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

---

추천인을 저장하는 parentMap(key = 판매원, value = 추천인)과 총 이익을 저장하는 priceMap(key = 판매원, value = 이익)을 만든다.

enroll, referral 을 탐색하며 parentMap을 세팅한다. 

seller, amount 배열을 탐색하며 priceMap 을 세팅해보자.

얻은 이익은 칫솔가격이 100이므로 amount[i] * 100이다. 이익의 10프로를 제외한 가격을 자신한테 더하고 10프로는 추천인한테 배분한다. 만약 parentMap[탐색중인 판매원] value가 "-"가 아닌 경우 이익의 분배를 다시 해야하므로 parentMap[탐색중인 판매원]를 탐색하며 다시 이익을 재분배한다. 이를 추천인이 없는 경우까지 반복한다.

모든 seller에 대해 위 알고리즘으로 priceMap을 구하면 enroll 배열의 판매원 순서대로 총이익을 배열로 만들면 정답이 된다.

 

이렇게 하면 정답은 구할수있지만 TC 11, 12, 13이 시간초과가 뜬다.

시간을 줄일 방법을 알기위해 제한사항을 자세히 읽어보자.

enroll은 10,000 이하. seller는 100,000 이하. amount는 100 이하이다.

[그림 1]

추측해볼 수 있는 시간낭비는 추천인이 [그림 1]과 같은 경우다.

하나의 판매에 무려 |enroll| 만큼의 시간이 소요될 것이다. 시간복잡도로 따져보면 priceMap을 구하는데 O(100,000 * 10,000) 만큼의 시간이 든다. TLE가 발생할것이다.

(여담이지만, Union-Find 알고리즘의 find 함수에서도 위와 같은 문제가 있어서 부모 배열에 직속 부모번호가 아닌 최상위 부모를 저장한다.)

수익을 배분할 때, 10퍼를 원 단위에서 절사한다. amount의 최대값은 100이고 칫솔의 가격은 100이기 때문에 한 번 판매의 최대 수익은 10,000일 것이다. 이를 10퍼씩 분배를 계속 해나가면 4, 5번만에 0이 될 것이다. 즉, 추천인이 [그림 1]과 같은 경우라도 최대 5번의 탐색만 발생할 것이다. 

이익의 0원인 경우 이익 배분을 종료하는 가지치기 코드를 넣으면 TLE를 해결할 수 있다.

 

시간복잡도는 N = |enroll|, M = |seller| 라 한다면 O(N + M). 부모노드에게 돈을 배분하는데에 최대 4, 5 번정도 들어서 O(N + KM) 이지만 K는 생략했다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/programmers/Dev-matching/%EB%8B%A4%EB%8B%A8%EA%B3%84%20%EC%B9%AB%EC%86%94%20%ED%8C%90%EB%A7%A4.cpp