다단계 칫솔판매 [자바]

 

🧫 문제 분석

✔️ 출처

다단계 칫솔 판매 level 3

📖 문제

seller가 판 이익의 10%을 계산

자신이 90%을 먹고 

자신의 추천인 즉, 부모에게 10%을 준다.

 

간단하게 자신의 부모를 가지는 배열을 생성하고

판매금에 대한 이익 90%을 가지고 부모에게 10%을 줘서 처리하면된다. 

 

 

여기서 간과한게 있는데 

처음에는 그냥 판매자의 최종 판매액을 합산해서 한 번에 계산하는게 빠르지 않을까 싶었는데

틀렸다. 생각해보니 문제에서 원단위 즉, 1원 미만은 절삭한다하였다. 

 

홀수 금액의 경우 

합산시 짝수가 될 수 있다. 

즉 A, B 금액 둘다 홀수라서 1원 미만은 절삭될 수 있고 

A+B를 합쳐서 계산시 짝수가 될 경우 위의 1원 미만 절삭이 사라져 오히려 더 큰 값이  분배될 가능성이 있다.

 

즉, 홀수 금액이 합산되어 짝수가 되면, 개별 분배 시 절삭되었을 1원이 합산 시 살아나 오히려 더 많은 금액이 분배된다.

---

🔅 문제 풀이

import java.util.*;
 
class Solution {
    static Map<String, Integer> map = new HashMap<>();
    static Map<String, Integer> nameIdx = new HashMap<>();
    static int[] parents;
    
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int[] answer = new int[enroll.length];
        parents = new int[enroll.length];
    
        for (int i = 0; i < enroll.length; i++) {
            nameIdx.put(enroll[i], i);
        }
        
        // 부모 설정 
        for (int i = 0; i < referral.length; i++) {
            String parent = referral[i];
            if (parent.equals("-")) {
                parents[i] = -1;
            } else {
                parents[i] = nameIdx.get(parent);
            }
        }
        
        for (int i = 0; i < seller.length; i++) {
            int idx = nameIdx.get(seller[i]); // 판매자의 인덱스 찾기 
            int cost = amount[i] * 100;
            
            // center 전 까지 탐색
            while (idx != -1) {
                int benefit = cost / 10;
                int mine = cost - benefit;
                answer[idx] += mine;

                if (benefit < 1) break; // 더 이상 분배 불가
                idx = parents[idx];
                cost = benefit;
            }
        }
        
        
        return answer;
    }
}

 

 

🔅 리팩토링

❗ 오답노트 / 필요한 지식

1. 항상 나누기를 조심하자. 나누기, 소수같은 문제가 나오면 의심하고 항상 여러방향으로 생각해보자.