[Algorithm/Programmers] 자바 - 다단계 칫솔 판매

문제	플랫폼	난이도	유형	풀이 링크	문제 링크
다단계 칫솔 판매	Programmers	2021 Dev-Matching: 웹 백앤드 개발자(상반기)	---	풀이	문제

문제 해석

서두의 문제 설명과 아래의 예시 그림으로 그래프 문제임을 쉽게 알 수 있습니다.
누가 얼마만큼의 이득을 가져갔는 지가 궁금하므로 각 노드의 이득(cost)를 관리해야할 거 같은 예감이 듭니다.

그래프를 슥 보고 지문을 마저 읽겠습니다.

문제를 풀 핵심 로직이 적혀있습니다.
1. 모든 판매원은 이익의 10%를 자신을 조직에 참여시킨 추천인에게 배분 한 뒤, 나머지를 자신이 가집니다.
2. 자신이 조직에 참여시킨 인원에게서 받은 이익또한, 자신의 이익에 포함되어 추천인에게 분배해야 합니다.
3. 10% 계산 시 원 단위 절사, 1원 미만일 경우 분배 X

2번 조항때문에, 피라미드의 최하단부터 모든 이익을 순차적으로 집계해야할 것 같습니다.

예제에서 이익 집계가 끝난 후의 그래프입니다.
이 결과가 파악하고자 하는 이익 배분 현황입니다.

주어진 input을 보고 문제를 풀어보도록 합시다.

제한 사항을 읽고 주의해야할 점들을 염두에 두고 시작하겠습니다.
1. 일단, 각 input의 의미를 잘 파악하도록 합시다.
2. enroll 배열에 민호가 없습니다.
3. enroll 배열은 조직에 참여한 순서를 따릅니다.
4. referral 배열에 추천인이 없는 사람이 올 수 있습니다.
5. seller 배열에 중복이 있을 수 있습니다.
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;
            }
        }
    }
}