[JAVA] 다단계 칫솔 판매

다단계 칫솔 판매

링크

프로그래머스

 

 

난이도 : Level 3

유형 : 트리, 재귀

코딩테스트 연습 > 2021 Dev-Matching: 웹 백엔드 개발자(상반기) > 다단계 칫솔 판매

 

문제 설명

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

각각은 자신을 조직에 참여시킨 추천인에 연결되어 피라미드 식의 구조를 이루고 있습니다. 조직의 이익 분배 규칙은 간단합니다. 모든 판매원은 칫솔의 판매에 의하여 발생하는 이익에서 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 글자 이내의 영문 알파벳 소문자들로만 이루어져 있습니다.

 

풀이

 

각자 자기가 번 돈에서 90프로만 가지고 추천인에게 10프로 주는 식으로 구조가 되어있고 모든 사람이 번 돈을 계산해봤을때 

최종적으로 각자 얼마를 가지고 있는지를 찾는 문제였다.

문제 그림에도 나와있듯이 트리구조를 사용하면 편할거같아서 써봤다. 각 사람의 이름, 추천인의 정보, 번 돈의 정보를 저장하는 Person 클래스를 만들어서 이어줬다. 그리고 HashMap을 사용해서 Person에 빠르게 접근할 수 있게 했다.

그렇게 트리구조로 연결을 해놨으면 자기가 번 돈의 10%는 떼고 저장한 후, 추천인이 없을 때까지 계속 위로 올라가면서 반복해주면 끝이었다. 

트리만 잘 활용하면 쉽게 풀 수 있는 문제인 것 같다. 

 

코드

import java.util.*;
class Solution {
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int[] answer = new int[enroll.length];
        // 각 판매원의 이름을 키로, Person 객체를 값으로 해서 빠르게 접근할 수 있게 함
        HashMap<String,Person> map = new HashMap<>();
        
        // map에 판매원의 이름을 key, 새로운 Person객체를 생성해서 넣음
        // referral[i]라는 key가 존재하지 않으면 .get은 null이 반환됨
        for(int i = 0; i < enroll.length; i++) {
            map.put(enroll[i],new Person(enroll[i],map.get(referral[i])));    
        }
        // 각 판매원에게 금액을 저장하고 추천인에게 10% 금액을 전달
        for(int i = 0; i < seller.length; i++) {
            Person p = map.get(seller[i]);
            Person boss = p.boss;
            int cost = amount[i]*100;
            
            // 추천인이 없을때까지
            while(true) {
                p.amount += cost - (cost/10);
                if(boss == null) break;
                cost = cost/10;
                p = boss;
                boss = p.boss;
            }
        }
        // enroll 순서대로 저장
        for(int i = 0; i < enroll.length; i++) {
            answer[i] = map.get(enroll[i]).amount;  
        }
        return answer;
    }
}
// 각 판매원의 정보를 저장하는 클래스
// 이름, 추천인, 누적금액을 저장
class Person {
    String name;
    Person boss;
    int amount;
    
    public Person(String name, Person boss) {
        this.name = name;
        this.boss = boss;
        this.amount = 0;
    }
}