[JAVA] 다단계 칫솔 판매

문제

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

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

내 풀이

import java.util.*;
class Solution {
     
    private static Map<String,String> ancestors = new HashMap<>();
    private static Map<String,Integer> incomes = new HashMap<>();

    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int[] answer = new int[enroll.length];
        
        for(int i=0; i<enroll.length; i++) {
            ancestors.put(enroll[i], referral[i]);
        }
        
        for(int i=0; i<seller.length; i++) {
            process_income(seller[i], amount[i] * 100);
        }
        
        for(int i=0; i<enroll.length; i++) {
            answer[i] = incomes.getOrDefault(enroll[i], 0);
        }
        
        return answer;
    }
    
    private void process_income(String name, int amount) {
        if (name.equals("-") || amount == 0) {
            return;
        }
        int share = amount / 10;
        incomes.put(name, incomes.getOrDefault(name, 0) + amount - share);
        process_income(ancestors.get(name), share);
    }
}

기본적으로 재귀를 이용한다.

ancestor 는 자식과 부모 관계를 정의한다. 여기서 자식은 소개받은 사람(enroll), Map의 값인 부모는 소개자다. (referral)

 

process_income은 판매자와 그 금액을 받아, 판매자의 이름과 돈의 양을 체크한 후, 유효하다면 

소개자에게 나눠줘야하는 금액 share를 계산한 후 나머지 금액은 수입으로 저장한다.

 

나눠줘야하는 금액과 나눠줘야하는 사람에 대해 이 process_income 을 반복한다.

알게 된 것

내 풀이가 다른 사람의 풀이에 뒤지지않게 깔끔하다고 생각했다.

 

피드백

그러나 재귀인만큼 효율성은 더 떨어질지도 모르겠다.

while문으로도 충분히 center (root node) 까지 수익계산을 할 수 있을 것 같다.