[알고리즘 TIL] 다단계 칫솔 판매

문제

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

프로그래머스

프로그래머스 lv2. 그래프

설명

그래프를 탐색하는 간단한 문제이다. 이 문제를 풀면서 그래프 탐색 구현을 복습하며, 삼항 연산자로 코드를 간결하게 만들고, Math 라이브러리의 올림 함수도 적용해볼 수 있었다. 또한 시간 초과가 난 에제를 분배금이 0인 경우 바로 break하는 코드를 추가하며 해결했다.

구현

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

public class Q_다단계칫솔판매_그래프 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] enroll = new String[]{"john", "mary", "edward", "sam", "emily", "jaimie", "tod", "young"};
        String[] referral = new String[]{"-", "-", "mary", "edward", "mary", "mary", "jaimie", "edward"};
        String[] seller = new String[]{"young", "john", "tod", "emily", "mary"};
        int[] amount = new int[]{12, 4, 2, 5, 10};
        int[] answer = solution.solution(enroll, referral, seller, amount);
        System.out.println(Arrays.toString(answer));
    }

    static class Solution {
        public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
            int[] answer = new int[enroll.length];
            HashMap<String, String> graph = new HashMap<>();
            HashMap<String, Integer> earns = new HashMap<>();
            graph.put("center", "-");
            for (int i = 0; i < enroll.length; i++) {
                String enrollName = enroll[i];
                String referralName = referral[i];
                graph.put(enrollName, referralName.equals("-") ? "center" : referralName);
            }

            for (int i = 0; i < seller.length; i++) {
                //그래프를 거슬러 올라갈 때마다 갱신되는 데이터
                String sellerName = seller[i];
                int sellerAmount = amount[i] * 100;
                while (true) {
                    //시간 초과 방지를 위해 분배금이 없으면 바로 종료
                    if (sellerAmount == 0) {
                        break;
                    }
                    //center인 경우
                    if (graph.get(sellerName).equals("-")) {
                        Integer earn = earns.get(sellerName);
                        earns.put(sellerName, earn==null ? sellerAmount : earn + sellerAmount);
                        break;
                    }
                    //추천인이 있는 경우
                    //본인 0.9만, 나머지 0.1은 다음 반복문에 넘김
                    Integer earn = earns.get(sellerName);
                    earns.put(sellerName, earn==null ? (int)Math.ceil(sellerAmount*0.9) : earn + (int)Math.ceil(sellerAmount*0.9));
                    //갱신
                    sellerName = graph.get(sellerName);
                    sellerAmount -= (int) Math.ceil(sellerAmount * 0.9);
                }
            }

            for (int i = 0; i < enroll.length; i++) {
                Integer earn = earns.get(enroll[i]);
                answer[i] = (earn==null ?  0 : earn);
            }

            return answer;
        }
    }
}