[lv3] 다단계 칫솔 판매

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

 

특별한 알고리즘은 없는 단순 구현문제였다.

 

각 판매원을 Node로 치환하고 map으로 관리하면 쉬웠다.

문제 설명이 엄청 길어서 center라는 루트 노드가 존재함을 놓치지 말아야 한다.

 

import java.util.*;

class Node {
    Node parent;
    int money = 0;

    Node(Node parent) {
        this.parent = parent;
    }
}

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

        int E = enroll.length;
        int S = seller.length;

        Map<String, Node> map = new HashMap<>();

        for(String name : enroll)
            map.put(name, new Node(null));

        map.put("center", new Node(null));

        // 추천인
        for(int i=0; i<E; i++)
            map.get(enroll[i]).parent = referral[i].equals("-")? map.get("center") : map.get(referral[i]);

        int price = 100;

        for(int i=0; i<S; i++) {
            Node now = map.get(seller[i]);
            int mul = price * amount[i];
            int per = mul / 10;
            int minus = mul - per;

            while(true) {

                // 추천인이 없거나, 10%가 1보다 작으면 모든 금액 추가
                if(now.parent == null || per < 1) {
                    now.money += mul;
                    break;
                }

                else {
                    now.money += minus;

                    now = now.parent;
                    mul = per;
                    per = mul / 10;
                    minus = mul - per;
                }
            }
        }

        int[] answer = new int[E];

        for(int i=0; i<E; i++) {
            answer[i] = map.get(enroll[i]).money;
        }

        return answer;
    }
}