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

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

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

[문제]

[풀이]

트리구조로 짜여진 다단계 구조에서 자기가 수익을내면 10%는 부모에게 올라가고
부모도 그 부모에게 10%가 올라가는 방식이다.

처음엔 단순 dfs 로 하려고 했다가 실패했다 .. 
한 사람이 두 번 이상 판매해서 수익을 발생시키고 그 수익금을 합쳐서 올리는게 아니라
따로따로 계산해서 1원미만 단위가 나오면 취급하지 않기 때문인데 .. 이게 무슨말이냐면

가령 , A라는 사람의 발생수익이 5원 5원이라고 하자. 그럼 10원이라서 그 부모에게 1원을 줘야하는데
여기선 따로취급해야하기 때문에 5원의 10%는 0원을 두 번 처리해야 된다는 뜻.

이것만 조심하면 풀 수 있다.

 

 
import java.util.*;
import java.io.*;
import java.util.stream.*;
 
 
class Solution {
    Map<String,Node> table;
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
 
        table = new HashMap<String, Node>();
        Node center = new Node("center",enroll.length);
        table.put("center",center);
 
        for(int i=0;i<enroll.length;i++) table.put(enroll[i],new Node(enroll[i],i));
 
        for(int i=0;i< referral.length;i++) {
            if(referral[i].equals("-")) table.get(enroll[i]).parent="center";
            else table.get(enroll[i]).parent = referral[i];
        }
        int[] result = new int[enroll.length];
        for(int i=0;i<seller.length;i++){
            int profit = amount[i]*100;
            Node cur = table.get(seller[i]);
 
            while (!cur.name.equals("center")){
                int parentProfit = profit/10;
                result[cur.key] += profit-parentProfit;
 
                cur = table.get(cur.parent);
                profit = parentProfit;
                if(profit<1) break;
            }
        }
        System.out.println("Arrays.toString(result) = " + Arrays.toString(result));
        return result;
    }
    static class Node{
        String name,parent;
        int key;
        public Node(String name,int key) {
            this.name = name;
            this.parent = null;
            this.key=key;
        }
    }
}