[프로그래머스] 다단계 칫솔 판매 - 자바(Java)

문제 링크

프로그래머스

문제 설명

민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, 조직을 운영하던 민호는 조직 내 누가 얼마만큼의 이득을 가져갔는지가 궁금해졌습니다. 예를 들어, 민호가 운영하고 있는 다단계 칫솔 판매 조직이 아래 그림과 같다고 합시다.

민호는 center이며, 파란색 네모는 여덟 명의 판매원을 표시한 것입니다. 각각은 자신을 조직에 참여시킨 추천인에 연결되어 피라미드 식의 구조를 이루고 있습니다. 조직의 이익 분배 규칙은 간단합니다. 모든 판매원은 칫솔의 판매에 의하여 발생하는 이익에서 10%를 계산하여 자신을 조직에 참여시킨 추천인에게 배분하고 나머지는 자신이 가집니다. 모든 판매원은 자신이 칫솔 판매에서 발생한 이익 뿐만 아니라, 자신이 조직에 추천하여 가입시킨 판매원에게서 발생하는 이익의 10%까지 자신에 이익이 됩니다. 자신에게 발생하는 이익 또한 마찬가지의 규칙으로 자신의 추천인에게 분배됩니다. 단, 10%를 계산할 때에는 원 단위에서 절사하며, 10%를 계산한 금액이 1원 미만인 경우에는 이득을 분배하지 않고 자신이 모두 가집니다.

(상세 예시 설명은 링크 확인 요망)

 

각 판매원의 이름을 담은 배열 enroll, 각 판매원을 다단계 조직에 참여시킨 다른 판매원의 이름을 담은 배열 referral, 판매량 집계 데이터의 판매원 이름을 나열한 배열 seller, 판매량 집계 데이터의 판매 수량을 나열한 배열 amount가 매개변수로 주어질 때, 각 판매원이 득한 이익금을 나열한 배열을 return 하도록 solution 함수를 완성해주세요. 판매원에게 배분된 이익금의 총합을 계산하여(정수형으로), 입력으로 주어진 enroll에 이름이 포함된 순서에 따라 나열하면 됩니다.

제한사항

• enroll의 길이는 1 이상 10,000 이하입니다.
  • enroll에 민호의 이름은 없습니다. 따라서 enroll의 길이는 민호를 제외한 조직 구성원의 총 수입니다.
• referral의 길이는 enroll의 길이와 같습니다.
  • referral 내에서 i 번째에 있는 이름은 배열 enroll 내에서 i 번째에 있는 판매원을 조직에 참여시킨 사람의 이름입니다.
  • 어느 누구의 추천도 없이 조직에 참여한 사람에 대해서는 referral 배열 내에 추천인의 이름이 기입되지 않고 “-“ 가 기입됩니다. 위 예제에서는 john 과 mary 가 이러한 예에 해당합니다.
  • enroll 에 등장하는 이름은 조직에 참여한 순서에 따릅니다.
  • 즉, 어느 판매원의 이름이 enroll 의 i 번째에 등장한다면, 이 판매원을 조직에 참여시킨 사람의 이름, 즉 referral 의 i 번째 원소는 이미 배열 enroll 의 j 번째 (j < i) 에 등장했음이 보장됩니다.
• seller의 길이는 1 이상 100,000 이하입니다.
  • seller 내의 i 번째에 있는 이름은 i 번째 판매 집계 데이터가 어느 판매원에 의한 것인지를 나타냅니다.
  • seller 에는 같은 이름이 중복해서 들어있을 수 있습니다.
• amount의 길이는 seller의 길이와 같습니다.
  • amount 내의 i 번째에 있는 수는 i 번째 판매 집계 데이터의 판매량을 나타냅니다.
  • 판매량의 범위, 즉 amount 의 원소들의 범위는 1 이상 100 이하인 자연수입니다.
• 칫솔 한 개를 판매하여 얻어지는 이익은 100 원으로 정해져 있습니다.
• 모든 조직 구성원들의 이름은 10 글자 이내의 영문 알파벳 소문자들로만 이루어져 있습니다.

입출력 예

enroll	referral	seller	amount	result
["john", "mary", "edward", "sam", "emily", "jaimie", "tod", "young"]	["-", "-", "mary", "edward", "mary", "mary", "jaimie", "edward"]	["young", "john", "tod", "emily", "mary"]	[12, 4, 2, 5, 10]	[360, 958, 108, 0, 450, 18, 180, 1080]
["john", "mary", "edward", "sam", "emily", "jaimie", "tod", "young"]	["-", "-", "mary", "edward", "mary", "mary", "jaimie", "edward"]	["sam", "emily", "jaimie", "edward"]	[2, 3, 5, 4]	[0, 110, 378, 180, 270, 450, 0, 0]

 

문제 풀이

[고려사항]

enroll, referral는 최대 10,000(1만)이고, seller는 100,000(10만) 때문에 시간 복잡도를 고려하여 구현해야한다.

[알고리즘, 구현방법]

판매원의 이름을 key값으로 해서 각 판매원의 정보를 저장한다.

판매원 정보로는 판매원을 조직에 참여시킨 다른 판매원의 이름과 판매원의 누적 이익금을 포함시킨다.

판매량 집계 데이터의 판매원 이름 정보인 seller를 기준으로 판매액을 분배해야하기 때문에, 각 판매원이 이익을 분배해야하는 다른 판매원 정보를 가지고 있어야한다.

 

판매원 정보 저장한 후 seller 정보를 기준으로 수익금을 배분한다.

예를 들어, young은 위로 3명의 판매원이 걸쳐매있기 때문에 총 4인이 이익금을 나눠가져야한다.

young이 1,200원의 이익금을 벌었다면, young은 10%를 제외한 1,080원 / young의 바로 위 판매원에게는 10%를 제외한 (120-12)108원 / 그 위 판매원에게는 10%를 제외한 (12-1)11원 / 그리고 가장 위인 center에는 1원을 분배해야한다.

즉 각 판매원이 가지는 이익금은 본인에게 할당된 금액의 10%를 제외한 금액이고, 10%만큼의 금액은 그 위 판매원에게 할당되어야한다.

 

X 1차 생각

아래 과정을 재귀 함수로 호출해서 수행하면 정답이 나오긴 하지만, 시간 복잡도가 O(mn)이 되어 시간 초과로 실패한다.

1. 해당 판매원에게 할당되는 이익금의 10%제외한 금액을 판매원 이익금에 누적합
2. 해당 판매원의 referral 판매원에게 10%를 제외한 금액을 할당
3. referral 판매원으로 1을 다시 수행
4. 판매원 정보에 referral이 없을때까지 수행 (=center)

public static int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        // 1. 판매원 정보 저장
        for (int i=0; i<enroll.length; i++) {
            sellerInfoMap.put(enroll[i], new SellerInfo(referral[i]));
        }
        // 2. seller 판매액 분배
        for (int i=0; i<seller.length; i++) {
            distributeProfits(seller[i], amount[i] * 100);
        }
        // 3. 결과
        int[] answer = new int[enroll.length];
        for (int i=0; i<enroll.length; i++) {
            answer[i] = sellerInfoMap.get(enroll[i]).getProfits();
        }
        return answer;
    }
    public static void distributeProfits(String seller, int profits) {
        // 해당 판매원에게 할당되는 이익금의 10% 제외한 금액을 판매원 이익금에 누적합
        int excludingTen = profits / 10;
        int netProfit = profits - excludingTen;

        SellerInfo s = sellerInfoMap.get(seller);
        s.addProfits(netProfit);

        if (s.getReferral().equals("-")) return; // 최상위 판매원(center)은 이익금 결과로 없어도 됨

        distributeProfits(s.getReferral(), excludingTen); // 해당 판매원의 referral 판매원에게 10%를 제외한 금액을 할당
    }

distributeProfits 함수를 seller 길이만큼 호출하고, 함수 내부에서는 최대 깊이가 총 판매원 수(=enroll 길이)이므로, 최악의 경우 seller 최대 길이 100,000(10만) * enroll 최대 길이 10,000(1만) = 1,000,000,000(10억)이므로 시간 초과가 뜬다.

즉, 시간 복잡도O(mn)으로 실패한다. (m = seller 길이, n = enroll 길이)

 

✅ 2차 생각

seller를 순회하면서 각 seller에 대한 이익금 분배를 BFS로 수행하면 시간 복잡도를 O(m+n)으로 줄일 수 있다.

각 판매원에 대해 BFS 순회를 1번만 하기때문에 m(seller 길이) + n(enroll 길이)로 수행할 수 있는 것이다.

재귀 호출의 경우 깊이 탐색으로 함수를 계속적으로 호출하므로 스택 오버 플로우의 위험도가 증가한다.

반면 BFS로 하면 Queue를 사용하여 한번에 처리하므로, 각 판매원을 여러번 호출하는 오버헤드가 줄어든다.

그리고 탈출 조건으로 더이상 분배할 이익금이 없는 경우도 추가한다.

해당 조건을 추가함으로써 불필요한 반복문 수행을 없앤다.

 

[풀이 과정]

1. 판매원 정보 저장
   • 판매원 정보: 해당 판매원을 추천한 판매원 정보(referral), 해당 판매원의 이익금(profits)
2. seller 순회하면서 판매액 분배
   • 이익금을 얻은 판매원(seller)의 상위 판매원들을 모두 BFS로 순회하면서 이익금을 규칙에 맞게 할당
3. 결과 출력

 

정답 코드

static Map<String, SellerInfo> sellerInfoMap = new HashMap<>();
public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
    // 1. 판매원 정보 저장
    for (int i=0; i<enroll.length; i++) {
        sellerInfoMap.put(enroll[i], new SellerInfo(referral[i]));
    }
    // 2. seller 판매액 분배
    for (int i=0; i<seller.length; i++) {
        distributeProfits(seller[i], amount[i] * 100);
    }
    // 3. 결과
    int[] answer = new int[enroll.length];
    for (int i=0; i<enroll.length; i++) {
        answer[i] = sellerInfoMap.get(enroll[i]).getProfits();
    }
    return answer;
}
public void distributeProfits(String seller, int profits) {
    Queue<String> queue = new LinkedList<>();
    queue.offer(seller);
    int currentProfit = profits;

    while (!queue.isEmpty() && currentProfit > 0) { // 더이상 분배할 판매원이나 이익금이 없을때까지 반복
        String currentSeller = queue.poll();
        // 해당 판매원에게 할당되는 이익금의 10% 제외한 금액을 판매원 이익금에 누적합
        int excludingTen = currentProfit / 10;
        int netProfit = currentProfit - excludingTen;

        SellerInfo s = sellerInfoMap.get(currentSeller);
        s.addProfits(netProfit);

        currentProfit = excludingTen;
        if (!s.getReferral().equals("-")) { // 최상위가 아닌 경우에 Queue에 판매원 추가
            queue.offer(s.getReferral());
        }
    }
}
public class SellerInfo {
    private String referral;
    private int profits;
    public SellerInfo(String referral) {
        this.referral = referral;
        this.profits = 0;
    }
    public void addProfits(int profits) {
        this.profits += profits;
    }
    public String getReferral() {
        return referral;
    }
    public int getProfits() {
        return profits;
    }
}