이번에 풀어본 문제는
프로그래머스 다단계 칫솔 판매 입니다.

📕 문제 링크

❗️코드

import java.util.*;

class Solution {
    static Map<String, String> parents;
    static Map<String, Integer> total;
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        parents = new HashMap<>();
        total = new HashMap<>();
        total.put("center", 0);

        int enrollSize = enroll.length;
        for (int i = 0; i < enrollSize; i++) {
            String child = enroll[i];
            String parent = referral[i];
            total.put(child, 0);

            if (parent.equals("-")) parents.put(child, "center");
            else parents.put(child, parent);
        }

        int sellerSize = seller.length;

        for (int i = 0; i < sellerSize; i++) {
            String member = seller[i];

            dfs(member, amount[i] * 100);
        }
        int[] answer = new int[enrollSize];
        for (int i = 0; i < enrollSize; i++) answer[i] = total.get(enroll[i]);
        return answer;
    }
    static void dfs(String child, int amount) {
        if (child.equals("center")) return;

        String parent = parents.get(child);
        int toParent = amount / 10;
        int tmpSum = amount - toParent;

        if (toParent > 0) dfs(parent, toParent);
        else tmpSum += toParent;

        total.put(child, total.getOrDefault(child, 0) + tmpSum);
    }
}

📝 풀이

다단계 조직에서 칫솔을 판매할 때, 자신을 소개해준 사람에게 판매액의 10%를 떼어주게 됩니다.
한 사람의 판매액이 최상위 소개자에게 까지 계속해서 분배된다고 할 때, 누적 합산 금액을 인원별로 반환하는 문제입니다.
그래프 상태로 보면 1:N 관계 같지만, 결국 나의 판매액을 분배해야하는 대상은 각각 1:1로 이루어져 있기 때문에 Map 자료구조로 표현해보았습니다.
결과적으로, 모든 연관관계를 표현해준 후, 판매액별로 깊이 탐색을 통해 보낼 수 있는 최상위 레벨까지 돈을 분배해주는 반복을 완료하고, 마지막 결과를 반환하면 해결할 수 있습니다.