출처 - 프로그래머스

1. 문제 이해

👯‍ 판매원과 추천인

• 위 그림의 트리 구조에서 자식 노드는 판매원, 부모 노드는 추천인을 의미한다.
• 예를 들어 young이라는 판매원은 edward가 추천했으며, edward라는 판매원은 mary가 추천했다는 의미다.
• mary, john의 추천인은 center라고 생각한다.

🤑 이익 구조

• 모든 판매원은 자신이 칫솔을 판매하고 생긴 이익에서 10%를 계산하여 추천인에게 배분하고 나머지는 자신이 가진다.
• 모든 판매원은 칫솔을 판매하고 생긴 이익 뿐만 아니라, 자신이 추천한 판매원에게서 배분 받은 이익금의 10%를 계산하여 자신의 추천인에게 배분한다.
• 이익의 10%를 계산할 때, 소수점 단위는 자신이 갖는다. 따라서 이익의 10%가 0원일 때는 추천인에게 배분할 필요가 없다.

🎊 요구하는 결과

최종적으로 모든 판매원들이 갖게 되는 각각의 이익들.

2. 문제 풀이

💾 data structure

1. 판매원의 이익금의 10%를 계산하여 추천인에게 배분해야 하기 때문에 각 판매원 별로 추천인이 누구인지 알아야 한다.
   • 따라서 hash table을 통해 <판매원, 추천인>의 관계를 저장한다.

2. 각 판매원 별로 자신이 얼마를 벌었는지 알아야 한다. 또한 10%의 이익금을 추천인에게 배분해서 온전히 자신의 이익이된 돈과 이제 10%의 이익을 추천인에게 배분해야할 돈 2가지로 나누어 정보를 가지고 있어야 한다.
   • 따라서 hash table을 통해 <판매원, {배분해야 할 돈, 배분을 마친 돈}>의 관계를 저장한다.

📜 알고리즘 (절차)

1. <판매원, 추천인>의 관계를 저장한 hash table referralMap을 만든다.
2. <판매원, {배분해야 할 돈, 배분을 마친 돈}>의 관계를 저장하기 위한 moneyMap을 만든다.
3. 칫솔을 판매한 사람들의 정보를 탐색한다.
   3-1. 해당 판매원의 이익금을 moneyMap[판매원][0]에 저장한다.
   3-2. 10%의 이익금을 떼고 나머지 금액을 moneyMap[판매원][1]에 저장한다.
   3-3. 떼어 낸 이익금을 moneyMap[referralMap[판매원]][0]에 저장한다.
   3-4. 판매원 = referralMap[판매원], 즉 추천인으로 바꾼다.
   3-5. 판매원 == "-" (center)가 아니라면 3-1로, 맞다면 3.으로 돌아간다.

3. 소스코드

CPP

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    int cntEnroll = (int)enroll.size();
    int cntSeller = (int)seller.size();
    vector<int> answer;
    unordered_map<string, string> referralMap;
    unordered_map<string, vector<int>> moneyMap; 
    
    moneyMap["-"] = vector<int>(2, 0);
    
    for (int i = 0; i < cntEnroll; i++)
    {
        string enr = enroll[i];
        string ref = referral[i];
        
        referralMap[enr] = ref;
        moneyMap[enr] = vector<int>(2, 0);
    }
    
    for (int i = 0; i < cntSeller; i++)
    {
        string sell = seller[i];
        int money = amount[i] * 100;
        
        moneyMap[sell][0] = money;
        
        while (sell != "-")
        {
            vector<int>& moneyVec = moneyMap[sell];
            
            int tenPercent = moneyVec[0] / 10;
            
            moneyVec[1] += moneyVec[0] - tenPercent;
            moneyVec[0] = 0;
            
            if (tenPercent == 0)
                break;
            
            sell = referralMap[sell];
            
            moneyMap[sell][0] = tenPercent;
        }
    }    
    
    for (int i = 0; i < cntEnroll; i++)
    {
        answer.push_back(moneyMap[enroll[i]][1]);
    }
    
    return answer;
}