https://school.programmers.co.kr/learn/courses/30/lessons/77486
각 판매원이 득한 이익금을 나열한 배열을 return
IDEA 1. Tree구조
최초 문제의 이미지를 보면서 Tree 구조를 직접 구현해서 풀 수 있겠다고 생각했다.
이름을 고려하여 Tree를 정렬된 상태로 유지하지 않으면 가장 하위에 존재하는 seller가 중복해서 등장할 때, 탐색 비용이 너무 크다고 생각했다.
따라서 정렬된 상태를 유지하는 Tree구조를 구현해야 하는데,
이미지 상의 Center 부분에 대한 처리의 모호함과 구현해야할 양의 방대함으로 인해서 포기했다.
IDEA 2. 재귀, Map응용
Map을 이용하여, 사람-추천인, 사람-이익 을 관리하는 방안을 생각했다.
우선, 판매가 발생했을때, 이익이 계산되는 과정을 살펴보자.
예시의 tod를 기준으로 생각해보자.
1. tod는 판매액의 일부를 추천인인 jaimie에게 배분한다.
2. jaimie는 1에 대한 금액의 일부를 추천인인 mary에게 배분한다.
2. mary는 2에 대한 금액의 일부를 center에게 배분한다.
즉, 추천인이 "-" Center가 나올때까지 추천인을 따라 이익 배분 과정이 발생한다.
이 과정을 재귀적으로 처리한다.
computeIfPresent
earn.computeIfPresent(person, (key, value) -> value + profit);
// 사람이름에 대한 Key을 찾아 value에 기존 value와 현재 이익금을 더하여 매핑
import java.util.*;
class Solution {
Map<String, Integer> earn; // 수익금을 저장
Map<String, String> relation; // 나와 추천인 사이의 관계 저장
final int ITEM_PRICE = 100;
public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
earn = new HashMap();
relation = new HashMap();
for(int i = 0 ; i < enroll.length; ++i){
relation.put(enroll[i], referral[i]);
earn.put(enroll[i], 0);
}
for(int i = 0 ; i < seller.length; ++i)
calculateSell(seller[i], amount[i] * ITEM_PRICE);
int[] answer = new int[enroll.length];
for(int i = 0 ; i < enroll.length; ++i)
answer[i] = earn.get(enroll[i]);
return answer;
}
final float CHARGE_RATE = 0.1f; // 수수료 비율
public void calculateSell(String person, int price){
int charge = (int)(price * CHARGE_RATE); // 수수료
int profit = price - charge; // 나의 이익금
// 판매에 대한 이익금을 추가한다.
earn.computeIfPresent(person, (key, value) -> value + profit);
String parent = relation.get(person);
// 추천인이 없다면, 남은 수수료를 가져갈 사람이 없다.
if(parent.equals("-"))
return;
// 수수료가 0원인 경우, 어차피 금액이 증가하지 않는다.
// 불필요한 재귀 호출을 막자.
if(charge == 0)
return;
// 추천인이 수수료를 가져간다.
calculateSell(parent, charge);
}
}