[Algorithm/Java] dev matching : 다단계 칫솔 판매

import java.util.HashMap;
class Solution {
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        HashMap<String, Integer> list = new HashMap<>();
        int[] recommander = new int[enroll.length];
        int[] answer = new int[enroll.length];

        for(int i=0; i<enroll.length; i++){
            list.put(enroll[i], i);
            answer[i]=0;
        }

       for(int i=0; i<referral.length; i++){

            if(referral[i].equals("-")){
                recommander[i]=-1;
                continue;
            }

            recommander[i]= list.get(referral[i]);
      }

        for(int i=0; i<seller.length; i++){

            int earnMoney = amount[i]*100;
            int distributeMoney =0;
            int currentMember = list.get(seller[i]);

            while(currentMember!=-1){
                distributeMoney = earnMoney / 10;
                earnMoney = earnMoney - distributeMoney;
                answer[currentMember]+= earnMoney;
                currentMember = recommander[currentMember];
                earnMoney = distributeMoney;
                if(earnMoney<1) break;
            }
        }


        return answer;
    }


}

다단계 조직 풀이 문제 풀이 과정

모든 판매원은 칫솔의 판매에 의하여 발생하는 이익의 10%를 계산하여 자신을 조직에 참여시킨 추천인에게 배분하고 나머지는 자신이 가진다.

이익을 얻는 방법

• 자신이 판매한 이익 90%
• 자신이 추천한 판매이익10%

주의할 사항

10%를 계산한 금액이 1원 미만인 경우 자신이 가집니다(이득분배X)

파라미터

판매원의 이름을 담은 배열 : enroll

추천인배열 : referral

판매량 집계 데이터

• 판매원 이름 : seller
• 판매 수량 : amount

리턴값

판매원이 득한 이익금나열한 배열 ( enroll에 이름이 포함된 순서에 따라 나열 )

제한 사항

enroll의 길이 1이상 10000이하 ( 민호<center> 는 포함되어있지 않다)

referral의 길이 = enroll길이

어느 누구의 추천도 없이 조직에 참여한 사람 ( center의 자식 -> 추천인의 이름이 '-' 이다)

추천인은 이미 enroll에 등장했음이 보장된다

판매량 집계에 해당하는 seller , amount 의 길이는 1이상 100000이하 ( 중복해서 같은 이름이 들어올 수 있다 )

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]

1. enroll 읽어 hashmap에 name, enroll 배열 index+1로 등록해서 저장
2. referral 읽어 -면 center 냅두고 다른 string값이면 map에서 조회해서 부모로 등록

위로 올라가는 관계는 필요하지만 아래로 내려가는 관계는 필요하지않기때문에 자식.부모=누구 이거만 저장하면 될듯

---

 

earnMoney < 1일때 break;해주는점
처음에 break를 return이라고 써서 자꾸 에러가 났다;;

 

 

 

---

import java.util.*;
class Solution {
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        
        int N = enroll.length;
        int M = seller.length;
        HashMap<String, ArrayList<String> > childs = new HashMap<>();
        HashMap<String, String> parents = new HashMap<>();
        HashMap<String, Integer> fee = new HashMap<>();
        for(int i=0; i<N; i++) {
            childs.put(enroll[i], new ArrayList<>());
            fee.put(enroll[i], 0);
        }
        fee.put("-",0);
        for(int i=0; i<N; i++){
            parents.put(enroll[i], referral[i]);
        }
        
        for(int i=0; i<M; i++) {
            String now = seller[i];
            int cost = amount[i]*100;
            while(true) {
                if(parents.containsKey(now)==false) break; // 루트
                
                int distribute = cost/10;
                int remain;
                if(distribute==0) {
                    // 1원 미만일 경우
                    remain = cost;
                    fee.put(now, fee.get(now)+remain);
                    break;
                }
                else {
                    remain = cost - distribute;
                    fee.put(now, fee.get(now)+remain);
                    cost = distribute;
                    now = parents.get(now);
                }
            }

        }
        int[] answer = new int[N];
        for(int i=0; i<N; i++){
            answer[i] = fee.get(enroll[i]);
        }
        return answer;
    }
}

ㅓ다시푼코드가 더 느리네..ㅎ 처음꺼처럼 해시값 int배열로 가져와서 푸는거로 해야겠다