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

문제 설명

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

문제 풀이

• DFS로 풀이하였다.
• 크게 2가지 함정이 존재하였다.

  1. 일반적인 DFS처럼 각 노드를 1번만 방문하도록 구현해서는 안된다.
     특정 노드에 하위 2개의 노드가 있다고 가정하자 일반적 DFS 구현에서 하위 노드들에서 각각
     13, 9 를 받아왔을떄 합으로 10%를 계산하면 2가 되지만 문제의 조건에서는 1 + 0으로 1이 되어야 한다.
  2. DFS를 진행하며 분배해야할 금액이 0일 경우 (10% 내림했을때) 재귀를 중단해야 한다. (더이상 의미 없음)

• 다행이 첫번째 함정은 인지했지만 두번째를 인지못하여 헤맸다..

소스 코드 (JAVA)

import java.util.*;

class Solution {
    int[] result;
    String[] name, parent;
    Map<String, Integer> map = new HashMap<>(); // 각 이름의 인덱스 구하기

    //진행하면서 분배
    public void dfs(int cur, int remain) {
        //10% 계산
        int next = remain / 10 ;
        int mine = remain - next;
        result[cur] += mine;
        String parentName = parent[cur];

        if (parentName.equals("-") || next == 0)
            return;

        for (int i = cur - 1; i >= 0; i--) {
            if (!name[i].equals(parentName))
                continue;
            dfs(i, next);
            break;
        }
    }


    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        //초기화
        name = enroll;
        parent = referral;
        result = new int[name.length];
        for (int i = 0; i < name.length; i++)
            map.put(name[i], i);

        //
        for (int i = 0; i < seller.length; i++) {
            String n = seller[i];
            int a = amount[i] * 100;
            int ind = map.get(n);
            dfs(ind, a);
        }
        return result;
    }
}