프로그래머스 - 다단계 칫솔 판매 (Lv.3)

문제 링크

• 다단계 칫솔 판매

문제 풀이

• 다단계 조직의 구성원들과 각 구성원을 추천한 인물들을 매칭하는 작업이 필요하다.
• 데이터 간의 관계를 파악하는 것이 중요하다. enroll 배열은 조직의 모든 구성원의 이름을 담고 있고, referral, seller 배열에 담긴 이름은 모두 enroll 배열에 있다. 따라서, 각 이름을 인덱스로 표현할 수 있다.
• seller 에 담긴 수익을 낸 구성원부터 트리를 타고 올라가듯이 추천인 탐색을 하며 수익 계산을 해야하고, 추천인이 없이 들어온 사람까지 수익 배분이 끝나야 하나의 로직을 클리어하게 된다.

구현(TC 2개 시간초과)

#include <string>
#include <vector>
#include <iostream>

using namespace std;

void convert_recommander_to_idx(vector<string>& enroll, int idx, vector<int>& referral_t, string name){
    int n = enroll.size();
    for(int i=0; i<n; i++){
        if(enroll[i] == name){
            referral_t[idx] = i;
        }
    }
}

void convert_seller_to_idx(vector<string>& enroll, int idx, vector<int>& seller_t, string name){
    int n = enroll.size();
    for(int i=0; i<n; i++){
        if(enroll[i] == name){
            seller_t[idx] = i;
        }
    }
}

void update_money(vector<int>& answer, vector<int>& seller_t, vector<int>& referral_t, int profit, int idx){
    int send_money = profit / 10;
    int my_money = profit - send_money;
    
    int seller_idx = seller_t[idx]; 
    answer[seller_idx] += my_money;
    
    
    int recommander_money = send_money;
    int recommander_idx = referral_t[seller_idx];
    
    vector<int> remain_list;
    while(recommander_idx != -1){
        remain_list.push_back(recommander_idx);
        recommander_idx = referral_t[recommander_idx];
    }
    
    int remain_idx;
    for(int i=0; i<remain_list.size(); i++){
        my_money = send_money - send_money / 10;
        send_money = send_money / 10;
        remain_idx = remain_list[i];
        answer[remain_idx] += my_money;
    }
}

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    
    int n = enroll.size();
    vector<int> referral_t(n);
    vector<int> answer(n, 0);
    
    string rname;
    for(int i=0; i<n; i++){
        rname = referral[i];
        if(rname=="-") {
            referral_t[i]=-1; // center
            continue;
        }
        convert_recommander_to_idx(enroll, i, referral_t, rname);
    }
    
    int sell_len = seller.size();
    vector<int> seller_t(sell_len);
    string sname;
    for(int i=0; i<sell_len; i++){
        sname = seller[i];
        convert_seller_to_idx(enroll, i, seller_t, sname);
    }
    
    for(int i=0; i<sell_len; i++){
        update_money(answer, seller_t, referral_t, amount[i]*100, i);
    }
    
    return answer;
}

개선한 점

• 본인에게 들어온 돈(실제로 판매한 돈 혹은 추천인으로부터 받은 돈)의 90%만 받고, 10%는 윗 단으로 보내는 로직을 재귀적으로 구현한다.
• 재귀적으로 구현하면 기저사례를 적용하여 재귀호출을 제한할 수 있어서 시간 초과 테스트 케이스를 해결할 수 있다.

구현(All Pass)

#include <string>
#include <vector>
#include <iostream>

using namespace std;

void convert_recommander_to_idx(vector<string>& enroll, int idx, vector<int>& referral_t, string name){
    int n = enroll.size();
    for(int i=0; i<n; i++){
        if(enroll[i] == name){
            referral_t[idx] = i;
        }
    }
}

void convert_seller_to_idx(vector<string>& enroll, int idx, vector<int>& seller_t, string name){
    int n = enroll.size();
    for(int i=0; i<n; i++){
        if(enroll[i] == name){
            seller_t[idx] = i;
        }
    }
}

void update_money(vector<int>& answer, vector<int>& referral_t, int seller_idx, int profit){
    // 기저사례: 나한테 들어온 돈이 0일때
    if(profit==0) return;
    // 기저사례: seller_idx==-1 인 경우
    if(seller_idx==-1) return;
    
    int send_money = profit/10;
    int my_money = profit - send_money;
    answer[seller_idx] += my_money;
    
    int nseller_idx = referral_t[seller_idx];
    update_money(answer, referral_t, nseller_idx, send_money);
}

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    
    int n = enroll.size();
    vector<int> referral_t(n);
    vector<int> answer(n, 0);
    
    string rname;
    for(int i=0; i<n; i++){
        rname = referral[i];
        if(rname=="-") {
            referral_t[i]=-1; // center
            continue;
        }
        convert_recommander_to_idx(enroll, i, referral_t, rname);
    }
    
    int sell_len = seller.size();
    vector<int> seller_t(sell_len);
    string sname;
    for(int i=0; i<sell_len; i++){
        sname = seller[i];
        convert_seller_to_idx(enroll, i, seller_t, sname);
    }
    
    int seller_idx;
    for(int i=0; i<sell_len; i++){
        seller_idx = seller_t[i];
        update_money(answer, referral_t, seller_idx, amount[i]*100);
    }
    
    return answer;
}

구현(Updated)

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

using namespace std;

void setProfit(map<string, string>& relation, map<string, int>& incomes, string worker, int money){
    if(worker=="-") return;
    if(money==0) return;
    
    int sendMoney = money/10;
    int myMoney = money - sendMoney;
    incomes[worker] += myMoney;
    string recommender = relation[worker];
    setProfit(relation, incomes, recommender, sendMoney);
}

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    vector<int> answer;
    // relation & incomes init
    map<string, string> relation;
    map<string, int> incomes; // 직원 별 수익
    for(int i=0; i<enroll.size(); i++){
        relation[enroll[i]] = referral[i];
        incomes[enroll[i]] = 0;
    }
    
    // distribute profits
    string worker; int profit;
    for(int i=0; i<seller.size(); i++){
        worker = seller[i];
        profit = amount[i] * 100;
        setProfit(relation, incomes, worker, profit);
    }
    
    for(int i=0; i<enroll.size(); i++){
        worker = enroll[i];
        answer.push_back(incomes[worker]);
    }
    
    return answer;
}