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

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

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

 

풀이 참고 링크 (https://dev-note-97.tistory.com/267)

 

 

 

- dfs 문제

 - 오랫동안 풀지 못했다.

 - 리프부터 루프까지 타고 올라가는 로직이 아직 자신이 없는 게 느껴졌다.

 - dfs 로 리프에서 루프까지 역으로 타고 올라가기 위한 조건들을 잘 기억해 두자 ( parent 의 존재, 탈출 조건 확인)

 - 탈출 조건 : parent 노드가 없거나 price 10으로 나누었을 때 0인 것.

 

import java.util.*;
class Solution {
    
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        HashMap<String, Person> people = new HashMap();
        people.put("-", new Person("-"));
        for (int i=0; i < enroll.length; i++) {
            people.put(enroll[i], new Person(enroll[i]));
        }
        
        int[] answer = new int[enroll.length];
        
        for (int i=0; i < referral.length; i++) {
            Person ep = people.get(enroll[i]);
            Person rp = people.get(referral[i]);
            ep.parent = rp;
        }
        
        for(int i=0; i < seller.length; i++) {
            addProfit(people.get(seller[i]), amount[i] * 100);
        }
        
        for(int i=0; i < enroll.length; i++) {
            Person p = people.get(enroll[i]);
            answer[i] = p.profit;
        }
        
        return answer;
    }
    
    class Person {
        String name;
        Person parent;
        int profit;
        public Person(String name) {
            this.name = name;
        }
    }
    
    private void addProfit(Person p, int amount) {
        if (p.parent != null && (amount / 10) > 0) {
            p.profit += amount - (amount / 10);
            addProfit(p.parent, (amount / 10));
        } else {
            p.profit += amount;
        }
    }
}