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

programmers.co.kr/learn/courses/30/lessons/77486

코딩테스트 연습 - 다단계 칫솔 판매

 

풀이

처음에는 트리 구조로 구현해야 하나 싶었지만, Person 객체를 정의하고 해시맵을 사용하여 간단하게 추천인 관계를 추적할 수 있도록 구현했다.

1) enroll과 referral로부터 정보를 가져와 people 해시맵을 채워넣고 추천인 관계 설정

2) 이익 배분

2-1) seller와 amount의 길이만큼 이익 배분 반복 시행

2-2) while문에서 추천인에게 더이상 이익을 배분할 수 없을 때까지 반복하여 이익을 배분

3) answer에 이익 결과값 담기

코드

import java.util.*;
class Solution {
    class Person {
        String name;
        int profit;
        String parent;
        public Person(String name){
            this.name = name;
            this.profit = 0;
            this.parent = null;
        }
    }
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int[] answer = new int[enroll.length];
        // key : 이름(String) , value : Person 객체
        HashMap<String, Person> people = new HashMap<>();
        
        // people에 민호 추가
        people.put("-",new Person("-"));
        // people에 나머지 사람들 추가
        for(int i = 0; i < enroll.length; i++){
            people.put(enroll[i], new Person(enroll[i]));
            people.get(enroll[i]).parent = referral[i]; // parent 관계 설정
        }
        
        // 이익 배분
        for(int i = 0; i < seller.length; i++){
            // 추천인에게 이익 배분
            String now = seller[i];
            int now_profit = 100 * amount[i];   // 현재 받을 수 있는 이익
            int next_profit = 0;    // 다음 추천인이 받을 수 있는 이익
            while(true){
                // 추천인에게 10%로 넘겨줄 금액이 안되거나, 추천인이 없으면 해당 이익 배분 종료
                if(now_profit < 10 || people.get(now).parent == null) {
                    people.get(now).profit += now_profit;
                    break;
                }
                // 추천인에게 가는 이익 = 현재의 10% (원 단위 절사)
                next_profit = now_profit / 10;
                // 현재 받을 수 있는 이익 = 원래 받을 수 있는 이익 - 추천인에게 가는 이익
                people.get(now).profit += now_profit - next_profit;
                // 추천인으로 now의 포인터 변경
                now = people.get(now).parent;
                // now_profit 변경
                now_profit = next_profit;
            }
        }
        
        // answer에 각각의 이익 담기
        for(int i = 0; i < enroll.length; i++){
            answer[i] = people.get(enroll[i]).profit;
        }
        
        return answer;
    }
}