프로그래머스 다단계 칫솔 판매(JAVA)

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

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

 

저는 해당 문제를 map과 재귀적인 방법을 이용해 문제를 해결하였습니다.

map을 통해 각각의 사람에 대한 배열 인덱스를 저장하여 이를 통해 결과값에 접근할 수 있도록 하였습니다.

parent배열을 통해 해당 인덱스의 사람이 판매를 하면 그 위에 누가 있는지를 가리켰습니다.

parent배열을 따라가면서 -1(root)가 나올때까지 재귀적으로 돈을 구하였습니다.

 

import java.util.*;
class Solution {
    private static void initEnroll(String[] enroll,Map<String,Integer> map){
        int index = 0;
        for(String str : enroll){
            map.put(str,index++);
        }
    }
    private static void initReferral(String[] referral,
                                     int[] parent,
                                     Map<String,Integer> map){
        int index = 0;
        for(String str : referral){
            if("-".equals(str)){
                parent[index++] = -1;
            }else{
                int parentIndex = map.get(str);
                parent[index++] = parentIndex;
            }
        }
    }
    private static void calMoney(int[] answer,
                                 int[] parent,
                                 int nowIndex,
                                int money){
        if(nowIndex == -1){
            return ;
        }
        answer[nowIndex] += money - money/10;
        calMoney(answer,parent,parent[nowIndex],money / 10);
    }
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int[] answer = new int[enroll.length];
        Map<String,Integer> map = new HashMap<>();
        initEnroll(enroll,map);
        int[] parent = new int[enroll.length];
        initReferral(referral,parent,map);
        // System.out.println(Arrays.toString(parent));
        for(int i = 0 ; i < seller.length ; i++){
            int nowIndex = map.get(seller[i]);
            calMoney(answer,parent,nowIndex,amount[i]*100);
        }
        return answer;
    }
}