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

문제 링크

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

문제 설명

링크 참조

제한사항

링크 참조

알고리즘: DFS

풀이

이 문제는 문제를 정확히 이해한다면 쉽게 풀 수 있는 문제다.

처음 나는 하위 노드에 값을 전부 더해서 그 값에 10%를 상위 노드에 전달해 주는 식으로 했다.
이런 식으로 풀었을 때 문제점은 무엇이냐? -> 10개의 하위 노드에서 10원씩 전달받았을 때
총합은 100원이다. 여기서 10%는 10원이기 때문에 상위 노드에 10원을 전달하고 그 노드가 다시 10%를 상위 노드에 전달하면 그 노드는 1원을 받는다. 그런데 10원씩 따로 상위 노드로 전달해 주면 1원씩 10번 받게 되고 원 단위에서 절사하기 때문에 상위 노드는 0원을 10번 받게 된다. 그래서 전자의 경우는 1원을 받지만, 후자의 경우는 0원을 받게 된다.

그렇기 때문에 나는 분배금 리스트를 상위 노드에 전달해 주는 식으로 문제를 해결했다.
ex) 하위 노드에서 10원씩 2개가 왔을 때, 현재 노드에서는 각각의 값에 10%를 해서 분배금 리스트에 넣어줬다. (당연히 현재 노드에 판매금의 10%도 분배금 리스트에 넣어줘야 함)

시간 복잡도를 계산했을 때 O(n^2)이고 n은 10000이기 때문에 가능한 풀이다.

주의할 점은 판매자가 중복되어서 나올 수 있다. 그렇기 때문에 판매자가 중복으로 여러 번 나왔을 때 또한 따로 분배금 리스트에 넣어줘야 한다.

소스 코드

import java.util.*;
class Solution {
    static HashMap<String, ArrayList<String>> tree = new HashMap<>();
    static HashMap<String, ArrayList<Integer>> seller_map = new HashMap<>();
    static HashMap<String, Integer> answer_map = new HashMap<>();
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int[] answer = new int[enroll.length];
        tree.put("center", new ArrayList<>()); //root node
        seller_map.put("center", new ArrayList<>());
        for(int i=0; i<enroll.length; i++) {
            tree.put(enroll[i], new ArrayList<>());
            seller_map.put(enroll[i], new ArrayList<>());
        }
        for(int i=0; i<referral.length; i++) {
            if(referral[i].equals("-")) tree.get("center").add(enroll[i]);
            else tree.get(referral[i]).add(enroll[i]);
        }
        for(int i=0; i<seller.length; i++) seller_map.get(seller[i]).add(amount[i] * 100);
        DFS("center");
        for(int i=0; i<enroll.length; i++) answer[i] = answer_map.get(enroll[i]);
        return answer;
    }
    
    static ArrayList<Integer> DFS(String name) {
        if(tree.get(name).size() == 0) {
            ArrayList<Integer> distri_list = new ArrayList<>();
            int final_profit = 0;
            for(int i=0; i<seller_map.get(name).size(); i++) {
                distri_list.add(seller_map.get(name).get(i) / 10);
                final_profit += seller_map.get(name).get(i);
            }
            for(int i=0; i<distri_list.size(); i++) final_profit -= distri_list.get(i);
            answer_map.put(name, final_profit);
            return distri_list;
        }
        ArrayList<Integer> distri_list = new ArrayList<>(); //분산금 list
        int final_profit = 0; //최종 금액
        for(int i=0; i<seller_map.get(name).size(); i++) {
            distri_list.add(seller_map.get(name).get(i) / 10);
            final_profit += seller_map.get(name).get(i);
        }
        for(int i=0; i<tree.get(name).size(); i++) {
            final_profit += sum(distri_list, DFS(tree.get(name).get(i)));
        }
        for(int i=0; i<distri_list.size(); i++) final_profit -= distri_list.get(i);
        answer_map.put(name, final_profit);
        return distri_list;
    }
    
    static int sum(ArrayList<Integer> cur, ArrayList<Integer> lower) {
        int sum = 0;
        for(int i=0; i<lower.size(); i++) {
            sum += lower.get(i);
            int distri = lower.get(i) / 10;
            if(distri != 0) cur.add(distri);
        }
        return sum;
    }
}