Programmers : 다단계 칫솔 판매

문제링크

풀이요약

트리

풀이상세

1. 문자에 대한 빠른 탐색을 위해 map을 사용한다. map의 value로는 struct를 통해 부모 노드, 현재까지의 수입, 자식 노드 백터를 구성하였다.

2. 트리 그래프를 형성한 후에는, 수입 발생원 부터, 부모에게 10%의 마진을 계속 보내는 재귀를 진행한다. 상납하는 금액이 0원 이하가 되거나, 현재 노드가 center 가 되는 경우 재귀를 종료한다.

3. enroll의 순서에 맞게, 현재 가진 금액을 answer 담아 반환한다.

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
struct Node {
    string p;
    int money;
    vector<string> child;
};
unordered_map<string,Node> m;

void go(Node &node, int p) {
    if(node.p == "없음") {
        node.money += p/10;
        return;
    }
    
    if(p <= 0) return;
    
    node.money += (p - (p/10));
    go(m[node.p], p/10);
}

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    vector<int> answer;
    Node node;
    // center 추가
    node.p="없음";
    node.money=0;
    m["center"] = node;
    for(int i=0; i<enroll.size(); i++) {
        Node node;
        node.p = referral[i] == "-" ? "center" : referral[i];
        node.money = 0;
        m[enroll[i]] = node;
        // 자식 추가
        m[referral[i]].child.push_back(enroll[i]);
    }
    
    int price = 100;
    for(int i=0; i<seller.size(); i++) {
        go(m[seller[i]], amount[i]*price);
    }

    for(int i=0; i<enroll.size(); i++) {
        answer.push_back(m[enroll[i]].money);
    }
    return answer;
}