[프로그래머스] 다단계 칫솔 판매

문제

 

풀이

import java.util.*;
class Solution {
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int len = enroll.length;
        int[] answer = new int[len];
        
        Map<String, String> parentMap = new HashMap<String, String>();
        for (int i = 0; i < len; i++) {
            parentMap.put(enroll[i], referral[i]);
        }
        
        Map<String, Integer> map = new HashMap<String, Integer>();
        
        for (int i = 0; i < seller.length; i++) {
            int sum = amount[i] * 100;
            divide(parentMap, map, seller[i], sum);
        }
        
        Iterator<String> iterator = map.keySet().iterator();
        while(iterator.hasNext()) {
            String person = iterator.next();
            for (int i = 0; i < len; i++) {
                if (enroll[i].equals(person)) {
                    answer[i] = map.get(person);
                }
            }
        }
        
        return answer;
    }
    
    public void divide(Map<String, String> parentMap, Map<String, Integer> map, String seller, int amount) {
        
        String parent = parentMap.get(seller);
        if (parent == null) {
            return;
        }
        
        int dividedAmount = amount / 10;
        if (dividedAmount == 0) {
            map.put(seller, map.getOrDefault(seller, 0) + amount);
            return;
        }
        
        map.put(seller, map.getOrDefault(seller, 0) + amount - dividedAmount);
        
        divide(parentMap, map, parent, dividedAmount);
    }
}

• 재귀를 통해 금액을 가장 루트노드에 도착할 때 까지 10:90으로 나누어 배분한다.

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