Programmers - 다단계 칫솔 판매(C++)

https://programmers.co.kr/learn/courses/30/lessons/77486?language=cpp 

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

 

풀이

map을 이용하여 부모-자식 관계를 확인,

판매수익이 발생한 seller부터 부모가 없을 때("-")까지 발생 수익의 10%로 넘겨줌

 

#include <string>
#include <vector>
#include <map>

using namespace std;

map<string, string> parent;
map<string, int> gain;

void update_gain(string now, int sell_gain) {
    if (now == "-")return;
    int delivery = sell_gain * 0.1;
    //자신이 가져가는 이득을 *0.9 -> 소수점 내림으로 오차가 생겼음
    gain[now] += sell_gain -delivery;
    //1원 미만의 경우 예외처리를 해주지 않아서 의미없는 0원이 부모로 전달되면서 시간초과 발생
    if (delivery ==0)return;
    update_gain(parent[now], delivery);
}

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++) {//누가 추천해줬는지
        parent[enroll[i]] = referral[i];
    }

    for (int i = 0; i < seller.size(); i++) {
        update_gain(seller[i], amount[i] * 100);
    }
    
    for(int i=0;i<enroll.size();i++){
        answer.push_back(gain[enroll[i]]);
    }
    
    return answer;
}