프로그래머스 2021 Dev-Matching 77486 - 다단계 칫솔 판매(트리 순회)

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

코딩테스트 연습 - 다단계 칫솔 판매

- 문제가 처음 나온 5달 전에는 못 풀었는데 지금은 너무 쉽게 풀었음

- 전체 트리를 정의하고, 노드 마다 번 돈을 읽어내려가면서 부모까지 순회하면서 fee를 더해준다. 여기서 민호까지 수수료를 전달해줘야 하므로 parent[0]은 -1로 해준 뒤 순회하는 함수의 basis로 사용해준다.

- 이름을 미리 인덱스로 파싱해두는 해쉬를 하나 선언해서 열거형처럼 써서 편하게 풀었다. 

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

unordered_map<string, int> umap; // 0은 민호
int parent[10001];
int totalEarn[10001];
vector<int> answer;

void giveFee(int idx, int money) {
    if(parent[idx] == -1) { // 민호면 돈 다 먹고 종료
        totalEarn[idx] = money;
        return;
    }
    
    int fee = money / 10; // 19 * 10% = 1
    totalEarn[idx] += money - fee;
    
    giveFee(parent[idx], fee);
}


// enroll 1만, seller 10만
vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    int mNum = enroll.size();
    int selNum = seller.size();
    
    // 1. 트리 만들고
    parent[0] = -1; // 민호는 부모없음
    for(int i = 0; i<mNum; ++i) {
        string mem = enroll[i];
        string refMem = referral[i];
        
        umap[mem] = i+1;
        parent[i+1] = umap[refMem];
    }
    
    // 2. 총 번 돈 읽으면서 부모에게 전달
    for(int i = 0; i<seller.size(); ++i) {
        string mem = seller[i];
        int sell = amount[i];
        
        giveFee(umap[mem], sell * 100);
    }
    
    // 3. 돈분배 결과 enroll 순서대로 answer배열에 담기
    for(int i = 0; i<mNum; ++i) {
        string mem = enroll[i];
        int earn = totalEarn[umap[mem]];
        answer.push_back(earn);
    }
    
    return answer;
}