문제

Programmers Lv3, 다단계 칫솔 판매

핵심

• 입력의 크기가 10,000이라 대략 $O(N^2)$이하 알고리즘을 사용한다.
• 다단계 칫솔 판매 문제로 등록인, 추천인, 판매인과 판매 수량이 주어진다. 수익의 90%는 자신이 갖고, 10%에 대해선 추천인에게 주어야 한다. 자신에게 할당된 수익과 배분할 수익을 잘 나누어 계산해야 한다.
  
• 추천인을 바로 알 수 있도록 미리 파싱해 두는 게 가장 중요하다. HashMap을 이용해서 등록인에 대한 추천인을 $O(1)$에 알 수 있게 한다. 위 그림은 아래와 같이 저장된다.

mary -
john -
young edward
jaimie mary
edward mary
sam edward
emily mary
tod jaimie

• 판매한 사람들을 순회하며 수익 할당과 배분을 재귀로 하였다. 추천인이 없거나("-") 더 이상 배분할 수익이 없을 때를 재귀 종료 조건으로 잡았다.

void recur(string name, int income, unordered_map<string, int>& profits, unordered_map<string, string>& parent) {
    if (name == "-" || income < 1)
        return;
    int fee = income * 0.1;
    profits[name] += income - fee;
    recur(parent[name], fee, profits, parent);
}

for (int i = 0; i < seller.size(); ++i) {
	recur(seller[i], 100 * amount[i], profits, parent);
}    

• 문제가 간단해서 아래와 같이 반복문으로도 쉽게 변환할 수 있다.

for (int i = 0; i < seller.size(); ++i) {
	int income = 100 * amount[i];
	string cur = seller[i];
	while (cur != "-" && income >= 1) {
		int fee = income * 0.1;
		profits[cur] += income - fee;
		income = fee;
		cur = parent[cur];
	}
}

개선

코드

C++

#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>

using namespace std;

void recur(string& name, int income, unordered_map<string, int>& profits, unordered_map<string, string>& parent) {
    if (name == "-" || income < 1)
        return;
    int fee = income * 0.1;
    profits[name] += income - fee;
    recur(parent[name], fee, profits, parent);
}

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    
    unordered_map<string, string> parent;
    unordered_map<string, int> profits;
    
    for (auto& e : enroll) {
        profits[e] = 0;
    }
    for (int i = 0; i < enroll.size(); ++i) {
        parent[enroll[i]] = referral[i];
    }
    for (int i = 0; i < seller.size(); ++i) {
        recur(seller[i], 100 * amount[i], profits, parent);
    }
    
    vector<int> ans;
    for (auto& e : enroll) {
        ans.push_back(profits[e]);
    }
    return ans;
}

Java

import java.util.*;

class Solution {
    
    public void recur(String name, int income, Map<String, Integer> profits, Map<String, String> parent) {
        if (name.equals("-") || income < 1) {
            return;
        }
        int fee = (int) (income * 0.1);
        profits.put(name, profits.get(name) + income - fee);
        recur(parent.get(name), fee, profits, parent);
    }

    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        Map<String, String> parent = new HashMap<>();
        Map<String, Integer> profits = new HashMap<>();
        
        for (String e : enroll) {
            profits.put(e, 0);
        }
        for (int i = 0; i < enroll.length; ++i) {
            parent.put(enroll[i], referral[i]);
        }

        for (int i = 0; i < seller.length; ++i) {
            recur(seller[i], 100 * amount[i], profits, parent);
        }
        
        int[] answer = new int[enroll.length];
        for (int i = 0; i < enroll.length; ++i) {
            answer[i] = profits.get(enroll[i]);
        }
        return answer;
    }
}