다단계 칫솔 판매

문제 정보

• 프로그래머스 Lv.3
• 구현
• 문제 링크

풀이 1

추천인이 누군지 매번 탐색할 수 없으므로, HashMap<String, String>을 하나 만들고, 판매원과 이익금을 매핑할 HashMap<String, Integer>을 하나 만들어서 사용했다.

코드

import java.util.*;
 
class Solution {
    Map<String, String> recommender; // <판매원, 추천인>
    Map<String, Integer> profit;
    
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        recommender = new HashMap<>();
        profit = new HashMap<>();
        
        // 판매원-추천인 매핑 및 이익금 초기화
        for (int i = 0; i < referral.length; i++) {
            recommender.put(enroll[i], referral[i]);
            profit.put(enroll[i], 0);
        }
        
        for (int i = 0; i < amount.length; i++) 
            settle(seller[i], amount[i] * 100);
        
        List<Integer> answer = new ArrayList<>();
        
        for(String name : enroll)
            answer.add(profit.get(name));
        
        return answer.stream()
            .mapToInt(Integer::intValue)
            .toArray();
    }
    
    /*
		이익금을 추천인에게 분배하는 함수
		피라미드를 타고 계속 분배되므로 재귀함수로 구현
    */
    private void settle(String beneficiary, int money) {
        if (money < 1) return;
        if (beneficiary.equals("-")) return;
        
        int commission = money / 10;
        
        if (commission >= 1)
            money -= commission;
        
        profit.put(beneficiary, profit.get(beneficiary) + money);
        
        settle(recommender.get(beneficiary), commission);
    }
}

• if (commission >= 1)에 대해서:
  • 이 부분은 실수다.
  • commission에는 나눗셈만 적용되기 때문에, 1보다 작다는 건 commission = 0이다. 그렇기에 money -= commission을 해도 무방하다.

풀이 2(인덱스 배열 기반)

앞선 풀이엔 다음과 같은 문제가 있다.

• 문제에서 가능한 최대 깊이가 10,000이기 때문에 재귀 호출 스택에 걸릴 수 있음
• Map.get()과 Map.put()이 반복되면서 속도가 떨어짐

이번 풀이는 인덱스 배열을 기반으로 하기 때문에 풀이 1보다 더 빠르다.

• Map<String, Integer>: 판매원과 그 판매원의 인덱스 매칭
• int[] parent: 판매원의 추천인(부모)의 인덱스를 저장

코드

import java.util.*;
 
class Solution {
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int n = enroll.length;
        
        // 판매원 이름 - 인덱스 매핑
        Map<String, Integer> index = new HashMap<>();
        for (int i = 0; i < referral.length; i++)
            index.put(enroll[i], i);
        
        // 추천인의 인덱스 저장. 추천인이 없으면 -1.
        int[] parent = new int[n];
        for (int i = 0; i < n; i++)
            parent[i] = referral[i].equals("-") ? -1 : index.get(referral[i]);
        
        int[] profit = new int[n];
        
        for (int i = 0; i < seller.length; i++) {
            int cur = index.get(seller[i]);
            int money = amount[i] * 100;
            
            while (cur != -1 && money > 0) {
                int commission = money / 10;
                profit[cur] += money - commission;
                money = commission;
                cur = parent[cur];
            }
        }
        
        return profit;
    }
}