(프로그래머스 C++)다단계 칫솔 판매

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

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

map과 dfs를 활용한 문제 풀이.

 

우선 enroll과 referral의 관계를 map 형태로 그려준다.

또한, cost라는 map을 이용해서 수익을 구할 것이다.

 

enroll과 referral을 for문으로 순회하면서 map을 형성.

key = enroll[i]로 하고, value = referral[i]로 저장한다.

만약 referral[i]가 "-"라면 value = "center"로 저장.

cost에도 enroll[i]를 key로 하고 value = 0으로 저장하여 초기화를 해주도록 한다.

 

이후 seller를 순회하면서 수익을 구하도록 한다.

seller[i]와 amount[i]를 이용하여 name과 money라는 변수에 저장한다.

money는 100을 곱해야 한다.

이제 dfs 함수에 name과 money를 넘겨주면서 다단계 수익 구조를 나타내도록 한다.

 

dfs()

먼저 종료 조건을 설정한다.

name = "center"라면 더 이상 탐색을 진행할 필요가 없기 때문에 return.

또한, money < 1이라면 모든 수익 구조를 name이 가져가고, 더 이상 분배를 안해도 되기 때문에 return.

 

나머지 조건은 탐색을 진행한다.

탐색 전에 cost[name] += money - floor(money * 0.1)을 해주어 10%를 뗀 나머지를 name이 가져간다.

이후 dfs에는 name을 추천한 사람인 m[name]과 money의 10%를 넘겨주면 알아서 윗 단계를 진행한다.

 

answer는 enroll의 순서대로 cost에서 value를 가져오면 된다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>

using namespace std;

map<string, string> m;
map<string, int> cost;
vector<int> answer;

void dfs(string name, int money){
    if(name == "center"){
        return;
    }
    
    if(money < 1){
        cost[name] += money;
        
        return;
    }
    
    cost[name] += money - floor(money * 0.1);
    dfs(m[name], floor(money * 0.1));
}

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    for(int i = 0; i < enroll.size(); i++){
        string e = enroll[i];
        string r = referral[i];
        
        if(r == "-"){
            m.insert({e, "center"});
        } else{
            m.insert({e, r});
        }
        
        cost.insert({e, 0});
    }
    
    for(int i = 0; i < seller.size(); i++){
        string s = seller[i];
        int money = amount[i] * 100;
        
        dfs(s, money);
    }
    
    for(int i = 0; i < enroll.size(); i++){
        answer.push_back(cost[enroll[i]]);
    }
    
    return answer;
}