[c++] Programmers - 다단계 칫솔 판매

2021 Dev-Matching: 웹 백엔드 개발자(상반기)
Lv.3 다단계 칫솔 판매

map 을 이용하여 재귀호출하는 문제!

단순히 추천인을 찾아가며 10퍼센트의 이익을 더해주는 문제이다.
그러나 시간초과로 계속 고생했는데,, 그 이유에는 여러가지 요인이있다.
간단히만 정리하자면

1. MAP을 사용할 것.

• 처음에는 index의 값을 저장하여 find함수를 이용하여 풀었으나, map을 사용하니 시간복잡도가 획기적으로 낮아짐 (map의 시간복잡도가 logN이라고 한다.)

2. 10%의 이익이 1 미만일때 호출 멈추기

• 최대 재귀 호출에 1000번정도의 제한되어 있기 때문!!
• 최악의 경우 (일직선 트리일 때 ) 불필요한 호출이 계속 될 수 있음

이것만 명시하면 난이도가 높을 문제는 아닐 듯 하다.
내가 MAP에 대한 지식이 부족했었던터라, 공부하여 앞으로의 문제에서 자주 활용 할 필요가 있을 듯 하다.

처음 코드 (11~13 케이스에서 Time Out)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

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++)
        answer.push_back(0);
    
    //seller 한 명 씩 계산
    for (int k=0; k<seller.size(); k++){
        string name = seller[k];
        int cost = amount[k]*100;
        
        //10%
        int per = cost / 10;
        cost -= per;
        
        int index = find(enroll.begin(), enroll.end(), name) - enroll.begin();
        
        while(cost != 0){ //반복
            
            answer[index] += cost;
            
            if (per < 1)
                break;
            
            //10%
            cost = per;
            per = cost / 10;
            cost -= per;
            
            //추천인 x
            if (referral[index] == "-")
                break;
            
            //다음 추천인
            index = find(enroll.begin(), enroll.end(), referral[index]) - enroll.begin();
        }
        
    }
    
    return answer;
}

정답 코드

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

using namespace std;

map <string, int> me;
map <string, string> par;

void dfs(string name, int cost){
    if (name == "-") return ;
    int ten = cost / 10;
    me[name] += cost - ten;
    
    if (ten > 0) dfs(par[name],ten);
}

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++){
        me[enroll[i]]=0;
        par[enroll[i]] = referral[i];
    }
    
    for (int i=0; i<seller.size(); i++){
        dfs(seller[i],amount[i]*100);
    }
    
    for (int i=0; i<enroll.size(); i++){
        answer.push_back(me[enroll[i]]);
    }
    
    return answer;
}