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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/77486

프로그래머스

 

---

 

문제 개요

민호는 다단계 방식으로 칫솔을 판매하는 조직을 운영하고 있습니다. 각 판매원이 칫솔을 판매하면, 발생한 이익이 추천인 관계를 따라 위로 분배되는 구조입니다. 이때 이익은 아래와 같은 규칙에 따라 분배됩니다.

• 칫솔 한 개를 판매하면 100원의 이익이 발생합니다.
• 이익의 10%는 추천인에게 전달되고, 나머지 90%는 본인이 가집니다.
• 이 추천인은 다시 받은 금액의 10%를 자신의 추천인에게 전달합니다.
• 이 과정은 분배 금액이 1원 미만이 될 때까지 반복됩니다.
• 10%는 항상 정수 단위로 내림 처리됩니다.

 

접근 방법

처음 에는 enroll 배열이 다단계에 들어온 사람의 순서이기 때문에 역순으로 순회하면서 계산하면 될 줄 알았다.

 

처음 코드

import java.util.*;
class Solution {
    static Map<String, String> myParent = new HashMap<>();
    static Map<String, Integer> money = new HashMap<>();
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int[] answer = new int[enroll.length];
        init(enroll, referral);
        sell(seller, amount);
        cal(enroll, answer);
        return answer;
    }
    
    public void cal(String[] enroll, int[] answer) {
        for(int i=enroll.length-1; i>=0; i--) {
            String cur = enroll[i];
            int curMoney = money.get(cur);
            int n = curMoney / 10;
            money.put(cur, curMoney - n);
            
            String parent = myParent.get(enroll[i]);
            if(n > 0 && !parent.equals("-")) {
                int pn = money.get(parent);
                money.put(parent, n + pn);
            }
        }
        
        for(int i=0; i<answer.length; i++) {
            String cur = enroll[i];
            answer[i] = money.get(cur);
        }
    }
    
    public void sell(String[] seller, int[] amount) {
        for(int i=0; i<seller.length; i++) {
            int n = money.get(seller[i]) + (amount[i] * 100);
            money.put(seller[i], n);
        }
    }
    
    public void init(String[] enroll, String[] referral) {
        for(int i=0; i<enroll.length; i++) {
            myParent.put(enroll[i], referral[i]);
            money.put(enroll[i], 0);
        }
    }
}

 

❌문제점

처음 작성한 코드는 판매자에게 먼저 전체 금액을 몰아넣고 반복문으로 모든 사람을 아래에서 위로 한 번만 분배하는 식이었으나, 문제에서 요구하는 것은 판매자가 물건을 팔면 수익의 10%를 자신의 추천인에게 주고, 추천인은 다시 자기 추천인에게 같은 방식으로 반복 분배되는 구조이기 때문에 계산하는 과정에서 잘못됐을 것이다.

 

최종 코드

import java.util.*;

class Solution {
    static Map<String, String> myParent = new HashMap<>();
    static Map<String, Integer> money = new HashMap<>();

    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int[] answer = new int[enroll.length];
        init(enroll, referral);

        for (int i = 0; i < seller.length; i++) {
            distribute(seller[i], amount[i] * 100);
        }

        for (int i = 0; i < enroll.length; i++) {
            answer[i] = money.get(enroll[i]);
        }

        return answer;
    }

    // 판매 수익 분배 - 재귀 방식
    public void distribute(String name, int income) {
        if (name.equals("-") || income < 1) return;

        int commission = income / 10;
        int myShare = income - commission;

        money.put(name, money.getOrDefault(name, 0) + myShare);
        distribute(myParent.get(name), commission);
    }

    // 부모 관계 및 초기화
    public void init(String[] enroll, String[] referral) {
        for (int i = 0; i < enroll.length; i++) {
            myParent.put(enroll[i], referral[i]);
            money.put(enroll[i], 0);
        }
    }
}

 

판매가 일어날 때마다 실시간으로, 위로 위로 재귀적으로 타고 올라가면서 분배하는 방식으로 변경했다.

사실 처음부터 생각한 방식이었지만

 

enroll의 최대 길이는 10,000이고 seller의 최대 길이는 100,000이라는 제한 사항만 보고 만약 민호(center)부터 한줄로 연결된 형태의 다단계라면 시간복잡도가 10,000 X 100,000 이지 않을까라는 생각을 해서 이렇게 풀지 않았다.

 

하지만 amount에 대한 제한 사항을 보면 각 원소들은 최대 100인 것을 알 수 있다. 그러면 각 최대 판매 수익은 10,000원이기 때문에 최대 5단계만 수행한다. 그래서 5 X 100,000이 되기 때문에 가능한 방법이었다.

1단계 분배: 1000원 (10%), 남은 9000원
2단계 분배: 100원
3단계 분배: 10원
4단계 분배: 1원
5단계 분배: 0원 → 멈춤