(C++) - 프로그래머스(2021 Dev-Matching: 웹 백엔드 개발자) : 다단계 칫솔 판매

https://programmers.co.kr/learn/courses/30/lessons/77486

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

backtracking 으로 푼 문제였습니다.

 

풀이방법

 1. 각 판매원들의 추천인들이 곧 graph로 따지면 parent node가 됩니다. 이 정보를 적절한 자료구조로 저장한다면 graph형태로 나타낼 수 있습니다. "-"는 root라고 생각하고 서순을 지키기 위해 unordered_map을 사용해 저장합니다.

 

 2. 모든 seller정보에 대해 이익을 갱신해줍니다. 부모 node로 거슬러 올라갈수록 현재 node의 돈의 0.1씩 줄어듭니다. 제일 처음 seller[i]부터 출발해 부모로 거슬러 올라가며 현재 확인하고 있는 사람의 이익을 갱신해줍니다. "-" 즉, root에 도착하거나 더 이상 부모 node에 나눠줄 돈이 없을 때 return해줍니다.

 

 3. 저장된 이익 정보를 answer에 push해주고 반환해줍니다.

Code

#include <bits/stdc++.h>
using namespace std;
unordered_map <string,string> parent;
unordered_map <string,int> profits;

void updateProfit(string name, int money){
    if(name == "-" || !money) return;
    int charge = money * 0.1;
    profits[name] += money - charge;
    updateProfit(parent[name], charge);
}

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    vector<int> answer;
    for(int i = 0; i < referral.size(); i++) parent[enroll[i]] = referral[i];
    for(int i = 0; i < seller.size(); i++) updateProfit(seller[i],amount[i] * 100);
    for(int i = 0; i < enroll.size(); i++) answer.push_back(profits[enroll[i]]);
    return answer;
}