문제 풀이

처음에 착각하기 쉬운게 트리를 구성해서 리프노드 까지 dfs로 파고 들어서 자식노드들의 수익을 모두 더해서 부모노드로 수익들을 올려줘야하나? 생각을 했지만 문제를 좀 더 꼼꼼하게 읽어보면 그럴 필요 없이 각 판매 내역마다 수익을 올려주기만 하면 된다.

HashMap을 이용해서 어떤 자식이 어떤 부모를 가지고 있는지에대한 정보를 저장하고
추가로 어떤 사람이 얼만큼의 수익을 가지는지에대한 정보도 저장한다.

어떤 사람이 수익을 내면 수익의 10%를 뗀 나머지는 자신이 가져가고 10%는 부모에게로 주면된다
이것은 재귀함수를 통해 구현하면된다. 단, 부모노드가 - 일 경우에는 더이상 수익을 전해줄 부모가 없으므로 종료, 수익이 0원이면 더 이상 전해줄 것도 없으므로 종료 해줘야한다.

문제 링크

Programmers/77486

소스코드

PS/Programmers/77486.java

 import java.util.*;

class Solution {
          static HashMap<String, String> map = new HashMap<>();
        static HashMap<String, Integer> result = new HashMap<>();
        static void givemoney(String now, int money)
        {
            if(now.equals("-"))
                return;
              if(money ==0 )
                return;
            String parent = map.get(now);
            int sum = money;
            int pres = sum * 10 /100;
            int mine = sum - pres;
            if(result.containsKey(now))
                result.put(now,result.get(now) + mine);
            else
                result.put(now,mine);
            givemoney(parent,pres);
        }
    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++)
            {
                map.put(enroll[i],referral[i]);
            }

            for(int i=0;i<seller.length;i++)
            {
                givemoney(seller[i],amount[i] * 100);

            }
            for(int i=0;i<enroll.length;i++)
            {
                if(result.containsKey(enroll[i]))
                answer[i] = result.get(enroll[i]);
                else
                    answer[i] =0;
                System.out.println(answer[i]);
            }

        return answer;
    }
}