프로그래머스 - 다단계 칫솔 판매 [C++]

 이 문제는 맵을 이용해서 풀었다. 내가 처음에 구현하려고 생각했던 방법은 sellCnt를 처음에 미리 다 더해서 한번에 구하는 것이었는데, 이 방법은 오답이다. 왜냐하면 나머지를 계산하는 과정에서 버림이 발생하고, 이로 인해 2, 2 를 따로 하는 것과 4 한번에 하는 것이 다르게 나올 수 있기 때문이다. 그래서 sellCnt 를 벡터로 바꿔주고, 각 enroll에 대해 인덱스를 계산하여 해당 사람으로부터 solve를 호출하여 answer에 누적하도록 하였다. 

 

 

 

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

using namespace std;

#define MAX 10000

map<string, int> peopleIndex;

int parent[MAX];
vector<int> sellCnt[MAX];
vector<int> answer;

void solve(int people, int cost) {
    if (people == -1) {
        return;
    }
    
    int reminder = cost / 10;
    int me = cost - reminder;
    answer[people] += me;
    solve(parent[people], reminder);
}

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    answer = vector<int>(enroll.size(), 0);
    
    for (int i = 0; i < enroll.size(); i++) {
        string& en = enroll[i];
        
        peopleIndex[en] = i;
        
        string& ref = referral[i];
        
        if (ref == "-") {
            parent[i] = -1;
        }
        else {
            int par = peopleIndex[ref];
            parent[i] = par;
        }
    }
    
    for (int i = 0; i < seller.size(); i++) {
        string& sel = seller[i];
        int am = amount[i];
        
        int people = peopleIndex[sel];
        sellCnt[people].push_back(am);
    }
    
    for (int i = 0; i < enroll.size(); i++) {
        string& en = enroll[i];
        
        int people = peopleIndex[en];
        
        if (sellCnt[people].empty()) {
            continue;
        }
        
        for (int sell : sellCnt[people]) {
            solve(people, sell * 100);
        }
    }
    
    return answer;
}