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

1. 문제 정보

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

프로그래머스

난이도 : 레벨 3

유형 : DFS

---

2. 문제 풀이

 

이 문제에서 핵심적인 부분은 3개이다.

숫자가 아닌 문자열로 되어있는 인덱스 정보로 그래프 노드끼리 어떻게 연결시킬까?
그래프 탐색 시 종료 조건은?
판매 정보에 중복이 있을 수 있다.

 

1. 문자열 정보로 그래프 노드 매핑

굳이 문자열을 숫자로 따로 매핑하는 과정을 거치지 않아도 간단히 그래프를 그릴 수 있다.

해쉬맵을 이용하여 그래프를 그려보자.

// A노드의 문자열 <> B노드의 문자열 
HashMap<String, String> edges

 

만약 "A"에 "B"가 연결된다면

"A"를 key로, "B"를 value로 그래프 간선 정보를 변환시켜 주면 된다.

 

필자는 bottom-up 구조로 그래프를 탐색할 것이기 때문에 key값을 자식으로, value를 부모로 설정한다.

 

2. 그래프 탐색 로직

seller 배열에 중복이 있을 수 있으므로 seller 배열을 순차탐색하여 그래프 탐색을 시작한다.

 

중요한 점은 top-down 방식처럼 부모노드가 연결된 모든 자식노드의 수수료를 받고 한 번에 계산하지 않을 것이다.

seller 배열에 중복이 있을 수 있으니 재귀 과정에서 넘어온 수수료를 바로 결괏값에 반영할 것이다.

 

예를 들어 seller 배열에 "A"라는 사람이 2번 있고 각각 판매량이 150, 150 일 때 경우

 

[따로 계산 시]
150 -> 15 -> 1 ->  0
150 -> 15 -> 1 ->  0
=> 1 + 1 = 2 수수료

[한 번에 계산 시]
300 -> 30 -> 3 -> 0
=> 3 수수료

 

위의 경우처럼 재귀 과정에서 부모 노드가 받는 수수료의 값이 달라진다.

 

 

배열을 탐색 시, 해당 원소를 시작 노드로 탐색을 시작한다.

자식 -> 부모 사이를 재귀 탐색하며 진행한다.

 

탐색 시 종료 조건은

1. 그래프의 루트 노드 도착 (루트 노드는 수수료를 줄 노드가 없기에 종료)

2. 자식으로부터 받은 수수료가 만약 0원이라면 종료 (자식으로부터 받은 수수료가 0이라면 굳이 계산을 하지 않아도 된다)

---

3. 코드

import java.util.Arrays;
import java.util.HashMap;

class Solution {

    HashMap<String, String> edges;
    HashMap<String, Integer> revenue;

    private void execDFS(String curPerson, int money) {
        if (curPerson.equals("-") || money == 0) { // 탐색 종료
            return;
        }

        int charge = money / 10; // 부모 노드에게 줄 수수료
        int myRevenue = money - charge; 자신의 수익

        revenue.put(curPerson, revenue.get(curPerson) + myRevenue); // 수익 정보 갱신
        execDFS(edges.get(curPerson), charge); // 부모 노드로 재귀 탐색 진행
    }

    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {

        edges = new HashMap<>();
        revenue = new HashMap<>();
        for (int i = 0; i < referral.length; i++) {
            edges.put(enroll[i], referral[i]); // 그래프 간선 정보 생성
            revenue.put(enroll[i], 0); // 결과값으로 사용, 매 탐색시 갱신
        }

        for (int i = 0; i < seller.length; i++) {
            execDFS(seller[i], amount[i] * 100);
        }

        int[] answer = new int[enroll.length];
        for (int i = 0; i < enroll.length; i++) {
            answer[i] = revenue.get(enroll[i]);
        }

        return answer;
    }

    public static void main(String[] args) {
        Solution test = new Solution();
        System.out.println(Arrays.toString(test.solution(
                new String[]{"john", "mary", "edward", "sam", "emily", "jaimie", "tod", "young"},
                new String[]{"-", "-", "mary", "edward", "mary", "mary", "jaimie", "edward"},
                new String[]{"sam", "emily", "jaimie", "edward"},
                new int[]{2, 3, 5, 4})));
    }
}