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

다단계 칫솔 판매(Level 3)

문제

전체 문제 보기

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

접근법

문제를 정확하게 이해하는 것이 중요합니다. 아래와 같은 상황에서 sam이 칫솔을 하나 판매했다면 mary의 소득은 1이 됩니다. 그리고 sam 이 칫솔을 10개 판매했다면 mary의 소득은 9가 됩니다.

문제는 여기서 mary가 칫솔을 5개씩 두 번 판매했다면 mary의 소득은 9가 아니라 5 + 5 = 10이 됩니다. 판매 건당 추천인들의 수익이 결정되는 것이지 판매인의 전체 수익으로 추천인의 수익이 결정되는 것이 아닙니다. 따라서 seller와 amount 원소 하나하나씩 부모노드에 소득을 책정해야 합니다. 이때 부모 노드와 각 노드의 수익을 해시 맵으로 정의하여 다음과 같이 계산할 수 있습니다.

전체 구현 코드

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

unordered_map<string, string> par;
unordered_map<string, int> profit;

void Sell(string name, int amount)
{
    if(amount <= 0 || name == "-") return;
    int tex = amount / 10;
    profit[name] += amount - tex;
    Sell(par[name], tex);
}
vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    vector<int> answer;
    int N = enroll.size();

    // 부모 연결
    for(int i = 0; i < N; ++i)
    {
        par[enroll[i]] = referral[i];
    }
    // 판매량 갱신
    for(int i = 0; i < seller.size(); ++i)
    {
        Sell(seller[i], amount[i] * 100);
    }
    // 정답 
    for(int i = 0; i < N; ++i)
    {
        answer.push_back(profit[enroll[i]]);
    }
    return answer;
}