[프로그래머스 Kit 풀이] Level 3 - 다단계 칫솔 (재귀)

# 주소

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

프로그래머스

# 문제

문제 설명

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

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

예를 들어, 아래와 같은 판매 기록이 있다고 가정하겠습니다. 칫솔의 판매에서 발생하는 이익은 개당 100 원으로 정해져 있습니다.

판매원판매 수량이익금

young	12	1,200 원
john	4	400 원
tod	2	200 원
emily	5	500 원
mary	10	1,000 원

판매원 young 에 의하여 1,200 원의 이익이 발생했습니다. young 은 이 중 10% 에 해당하는 120 원을, 자신을 조직에 참여시킨 추천인인 edward 에게 배분하고 자신은 나머지인 1,080 원을 가집니다. edward 는 young 에게서 받은 120 원 중 10% 인 12 원을 mary 에게 배분하고 자신은 나머지인 108 원을 가집니다. 12 원을 edward 로부터 받은 mary 는 10% 인 1 원을 센터에 (즉, 민호에게) 배분하고 자신은 나머지인 11 원을 가집니다. 이 상태를 그림으로 나타내면 아래와 같습니다.

그 후, 판매원 john 에 의하여 400 원의 이익이 발생합니다. john 은 10% 인 40 원을 센터에 배분하고 자신이 나머지인 360 원을 가집니다. 이 상태를 그림으로 나타내면 아래와 같습니다.

또 그 후에는 판매원 tod 에 의하여 200 원 이익이 발생하는데, tod 자신이 180 원을, 추천인인 jaimie 가 그 중 10% 인 20 원을 받아서 18 원을 가지고, jaimie 의 추천인인 mary 는 2 원을 받지만 이것의 10% 는 원 단위에서 절사하면 배분할 금액이 없기 때문에 mary 는 2 원을 모두 가집니다. 이 상태를 그림으로 나타내면 아래와 같습니다.

그 다음으로 emily 가 칫솔 판매를 통하여 얻은 이익 500 원은 마찬가지의 규칙에 따라 emily 에게 450 원, mary 에게 45 원, 그리고 센터에 5 원으로 분배됩니다. 이 상태를 그림으로 나타내면 아래와 같습니다.

마지막으로, 판매원 mary 는 1,000 원의 이익을 달성하고, 이 중 10% 인 100 원을 센터에 배분한 후 그 나머지인 900 원을 자신이 가집니다. 이 상태를 그림으로 나타내면 아래와 같습니다.

위와 같이 하여 모든 조직 구성원들의 이익 달성 현황 집계가 끝났습니다. 지금까지 얻은 이익을 모두 합한 결과를 그림으로 나타내면 아래와 같습니다.

이 결과가 민호가 파악하고자 하는 이익 배분 현황입니다.

각 판매원의 이름을 담은 배열 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 글자 이내의 영문 알파벳 소문자들로만 이루어져 있습니다.

입출력 예enrollreferralselleramountresult

["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]

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

입출력 예 #2

문제에 주어진 예시와 동일한 조직 구성에 조금 다른 판매량 집계를 적용한 것입니다. 이익을 분배하는 규칙이 동일하므로, 간단한 계산에 의하여 표에 보인 결과를 얻을 수 있습니다.

# 문제 해설 및 코드 리뷰

import java.util.*;
class Solution{
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount){
        int[] answer = new int[enroll.length];
        Map<String, String> parentMap = new HashMap<>();
        Map<String, Integer> memberIndexMap = new HashMap<>();
        for(int i = 0; i < enroll.length; i++){
            parentMap.put(enroll[i], referral[i]);
            memberIndexMap.put(enroll[i],i);
        }
        for(int i = 0; i < seller.length; i++){
            String now = seller[i];
            int profit = 100 * amount[i];
            while(!now.equals("-")){
                int profitParent = profit / 10;
                int nowProfit = profit - profitParent;
                answer[memberIndexMap.get(now)] += nowProfit;
                now = parentMap.get(now);
                profit = profit / 10;
                if(profit < 1)
                    break;
            }
        }
        return answer;
    }
}

문제의 사진에 나와 있는 것 처럼 각 노드의 입력이 주어졌을 때 추천인 코드를 부모 노드로 잡고 영업사원에 대한 이익을 추천인의 이익에 부여하는 문제입니다.

저는 자료구조를 도저히 뭘 써야 할지 몰라서 계속 헷갈려서 고민에 고민을 거듭하다가 결국 검색을 활용했습니다.

그리고 2개의 HashMap자료구조를 사용해야 하는 부분에서 크게 인상적인 느낌을 받았습니다.

살펴보겠습니다.

int[] answer = new int[enroll.length];
Map<String, String> parentMap = new HashMap<>();
Map<String, Integer> memberIndexMap = new HashMap<>();

answer[] 라는 배열의 크기는 enroll의 길이만큼 선언합니다.

answer[]배열은 정답이 될 것이기 때문에 enroll이라는 모든 멤버가 담긴 크기를 가져야 합니다.

HashMap은 위에 말씀드린대로 2개를 선언합니다.

parentMap은 멤버와 추천인 노드를 담을 것이며 memberIndexMap은 멤버를 담는데 이를 숫자로 담을 것입니다.

왜 그런지는 이후에 보겠습니다.

for(int i = 0; i < enroll.length; i++){
    parentMap.put(enroll[i], referral[i]);
    memberIndexMap.put(enroll[i],i);
}

이와 같이 parentMap에는 enroll[i]와 referral[i]의 각 인덱스를 삽입합니다.

memberIndexMap에는 enroll[i]을 삽입하고 i번째 멤버라는 것을 삽입할 것입니다.

따라서 parentMap과 memberIndexMp의 크기는 모두 같겠습니다.

for(int i = 0; i < seller.length; i++){
    String now = seller[i];
    int profit = 100 * amount[i];
    while(!now.equals("-")){
        int profitParent = profit / 10;
        int nowProfit = profit - profitParent;
        answer[memberIndexMap.get(now)] += nowProfit;
        now = parentMap.get(now);
        profit = profit / 10;
        if(profit < 1)
            break;
    }
}

이후 seller의 크기만큼 loop문을 돌리겠습니다.

now는 seller[i]로 잡고 profit은 amoun[i]에 100을 곱합니다.

이 profit이 이익이고 now는 현재의 판매자를 의미합니다.

(이유는 물건 한 개당 100원의 이익이기에 100을 곱하는 것입니다.)

그리고 만약 now가 -가 아니라면 (정상 판매자라면)

부모의 이익을 profitParent 로 잡고 profit 에 10을 나눈 수를 저장합니다.

이후 nowProfit은 profit에서 profitParent를 뺀 값이 되므로 기존의 profit의 9 / 10에 해당하는 값이 됩니다.

answer[memberIndexMap.get(now)] += nowProfit;
now = parentMap.get(now);
profit = profit / 10;
if(profit < 1)
    break;

이제부터가 중요한데, 두 번째로 선언했던 HashMap을 써볼 시간입니다.

memberIndexMap의 now에 해당하는 Value값을 잘 보시기 바랍니다.

이 Value값은 enroll의 i번째 멤버의 인덱스로 치환됩니다.

그리고 이것을 answer의 인덱스에 nowProfit을 더해주어 단계적으로 이익을 상위 레이어에서 처리할 수 있게 만들 수 있습니다.

또한 now는 더 위로 올라가기 위해, parentMap에 now를 넣고 얻어낸 Value값으로 지정합니다.

이에 따라 profit은 10으로 나누어 주어 해당 금액으로 이익을 분배해야 합니다.

그리고 만약 profit이 1보다 작아지면 버리기 때문에 break해주어 while문에서 빠져나오면 됩니다.

 

총평을 해보자면 이 문제는 노드 형식으로 되어 있는 부분을 많이 안 풀어봐서 그런지 어색한 느낌이었습니다.

다른 분들의 자료구조 선언과 설명을 보니 바로 아하 싶었지만 그 전엔 어떻게 자료구조를 선언해야할지, seller가 겹치면 어떻게 해결해야 할지, 상위 레이어로 이익을 올리려면 어떻게 해야할지 많이 헷갈렸습니다.

어떤 분께서는 dfs로 푸셔서 만약 "-"가 들어오면 return해버리고 seller가 정상적으로 들어오면 계속된 재귀로 이익을 올리시는 분도 계시더라고요. getOrDefault를 이용해서 최초의 HashMap에 데이터를 삽입할 때 seller의 크기만큼 for문을 돌려 재귀를 하시는 분도 계셨습니다.

getOrDefault를 이용하면 등록 안된 멤버들은 값이 모두 0으로 처리할 수 있다는 장점이 있습니다.

시간복잡도는 비슷할 것 같네요.

감사합니다.