[programmers] 다단계 칫솔 판매

문제 풀이 : 2021.06.06

풀이

동일 인물이 여러번의 수익을 냈을 때를 고려해야함
부모 노드로 수익을 보낼 때 해당 수익이 1보다 작아지면 다음부터는 0이 되므로 반복문 탈출 조건 추가 해야함
부모-자식 관계를 for문을 이용한 탐색으로 매번 찾게 되면 테스트케이스 11-13번이 시간초과됨 -> map에 저장하여 사용

코드

import java.util.*;
class Solution {
    static Map<String, String> sonParent = new HashMap<>(); 
    static Map<String, Integer> memberIndex = new HashMap<>();
    static int[] money;
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount){
        for(int i=0; i < enroll.length; i++){
            sonParent.put(enroll[i], referral[i]);
            memberIndex.put(enroll[i], i);
        }
        money = new int[enroll.length];
        for(int i = 0;i<seller.length;i++){
            divideMoney(seller[i],amount[i]);
        }
        return money;
    }
                          
    static void divideMoney(String seller, int amount){
        String son = seller;
        String parent = sonParent.get(son);
        
        int gain = amount*100;
        while(true){
            int parentGain = gain/10;
            int myGain = gain - parentGain;
            gain = parentGain;
            money[memberIndex.get(son)] += myGain;
            if(parent.equals("-") || gain <1 ) break;
            son = parent;
            parent = sonParent.get(son); 
        }
    }
}

문제 출처 링크