[Algorithm] Programmers :: 다단계 칫솔 판매

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

프로그래머스

map<string, pair<string, int>> parentMap;
 
void recur(string me, int money) 
{
    int parentMoney = money / 10;
    int myMoney = money - parentMoney;
    string parent = parentMap[me].first;
 
    parentMap[me].second += myMoney;
    
    if (parent != "no" && parentMoney != 0)
    {
        recur(parent, parentMoney);
    }
}
 
vector<int> solution(
    vector<string> enroll,   // 각 판매원 이름
    vector<string> referral, // 각 판매원을 조직에 참여시킨 판매원의 이름
    vector<string> seller,   // 판매량 집계 데이터의 판매원 이름
    vector<int> amount)      // 판매량 집계 데이터의 판매수량
{
    vector<int> answer;
 
    for (int i = 0; i < enroll.size(); i++)
    {
        if (referral[i] != "-")
        {
            parentMap[enroll[i]] = make_pair(referral[i], 0);
        }
        else
        {
            parentMap[enroll[i]] = make_pair("no", 0);
        }
    }
    
    for (int i = 0; i < seller.size(); i++)
    {
        recur(seller[i], amount[i] * 100);
    }
 
    for (int i = 0; i < enroll.size(); i++)
    {
        answer.push_back(parentMap[enroll[i]].second);
    }
 
    return answer;
}

 

map만 적절히 활용할 줄 알면 풀 수 있는 구현문제.

부모가 가질 이익금이 0원이라면 재귀를 돌릴필요가 없다.

불필요한 재귀를 방지해야 타임아웃에 안걸린다. 

recur함수의 'parentMoney != 0'의 조건을 빼버리면 타임아웃에 걸린다.