[Algorithm/Programmers]Java-多段歯ブラシ販売

問題プラットフォーム難易度タイプ解答リンク問題リンクマルチレベル歯ブラシ販売計画2021 Dev-Martching:Webバックエンド開発者(上半期)---に答える質問する

もんだいぶんせき

前述の問題の説明と以下の例の説明では、これがグラフィックの問題であることが容易にわかります.
各ノードの収益(コスト)を管理する必要がある場合があります.誰がどれだけのメリットを得たかを知りたいからです.

グラフを見て、指紋を読み終わります.

問題を解決するコアロジックが含まれています.
1.すべての営業担当者は、利益の10%を参加組織の推薦者に割り当て、残りは自分で所有します.
2.自分が組織に参加した者が得た利益は、自分の利益に推薦者に分配することも含まなければならない.
3.10%の計算で1元節約し、1元未満の場合Xを割り当てる
2つ目の条項のため、ピラミッドの一番下からすべての利益を順番に統計する必要があるかもしれません.

例の収益要約の終了後のグラフ.
この結果は、お客様が知りたい利益配分です.

与えられた入力を見て問題を解きましょう

私たちは読書制限を考慮し、注意すべき事項を考慮してから始めます.
1.まず、各入力の意味を把握しましょう.
2.登録手配に民浩はいない.
3.登録の順序は、参加組織の順序に従います.
4.推薦配列には推薦者がいない場合があります.
5.売り手の手配は重複する可能性がある.
6.すべての名前は10文字の小文字です.

に答える

import java.util.*;

class Solution {
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        
        int enrollLen = enroll.length;
        int sellerLen = seller.length;

        // Person 객체를 담는 people 해시맵 초기화
        HashMap<String, Person> people = new HashMap<>();
        int[] ans = new int[enrollLen];

        // 추천인이 없는 사람 추가
        people.put("-", new Person("-"));

        // 1. 트리 생성
        // 1.1 enroll 배열로 People 생성
        for (String name : enroll)
            people.put(name, new Person(name));

        // 1.2 referral 배열로 Person 객체 간 부모-자식 관계 초기화
        for (int i = 0; i < enrollLen; i++)
            people.get(enroll[i]).parent = people.get(referral[i]);

        // 2. 이익 계산
        for (int i = 0; i < sellerLen; i++)
            people.get(seller[i]).calcCost(amount[i] * 100);

        for (int i = 0; i < enrollLen; i++)
            ans[i] = people.get(enroll[i]).cost;
        
        return ans;
    }
    
    
    private static class Person {
        String name;
        Person parent;
        int cost;

        public Person(String name) {
            this.name = name;
            this.parent = null;
            this.cost = 0;
        }

        public void calcCost(int cost) {
            int costParent = cost / 10; // 부모에게 줄 이득

            if (costParent != 0 && this.parent != null) {
                this.cost += cost - costParent;
                this.parent.calcCost(costParent);
            } else {
                this.cost += cost;
            }
        }
    }
}