문제
https://school.programmers.co.kr/learn/courses/30/lessons/77486
입력
- 판매원의 이름을 담은 배열 enroll
- 판매원을 다단계 조직에 참여시킨 다른 판매원의 이름을 담은 배열 referral
- 판매량 집계 데이터의 판매원 이름을 나열한 배열 seller
- 판매량 집계 데이터의 판매 수량을 나열한 배열 amount
출력
각 판매원이 득한 이익금을 나열한 배열을 return
풀이
제한조건
- enroll의 길이는 1 이상 10,000 이하입니다.
- referral의 길이는 enroll의 길이와 같습니다.
- referral 내에서 i 번째에 있는 이름은 배열 enroll 내에서 i 번째에 있는 판매원을 조직에 참여시킨 사람의 이름입니다.
- 어느 누구의 추천도 없이 조직에 참여한 사람에 대해서는 referral 배열 내에 추천인의 이름이 기입되지 않고 “-“ 가 기입됩니다.
- seller의 길이는 1 이상 100,000 이하입니다.
- seller 에는 같은 이름이 중복해서 들어있을 수 있습니다.
- 칫솔 한 개를 판매하여 얻어지는 이익은 100 원으로 정해져 있습니다.
접근방법
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
Key값이 존재하고 null이 아니라면, key에 대한 새로운 값을 매핑한다.
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);
}
}