[프로그래머스] Lev 3. 다단계 칫솔 판매

 

MY TMI 😉

📑

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

코딩테스트 연습 - 다단계 칫솔 판매

 

신청해놓고 이력서 제출하는 걸 까먹어서 참여하지 못했던 웹 백엔드 데브매칭... 😂 2시간 시간을 가지고 실전처럼 풀어보았다. 

 

 

어떠한 사원을 추천한 사람(사원의 부모)은 한 명 밖에 없다는 점을 활용했다. 

 

우선, 각 사원에게 번호를 부여한다. 이를 기반으로, 자신의 추천인을 parent라는 배열에 추천인 번호를 저장한다. 이때 추천인이 없다면 ("-"),  parent 배열에 0 값을 넣어준다. 

 

그다음, 판매자와 칫솔 판매량 정보를 기준으로 아래와 같은 과정을 수행한다. 

 1. 판매자는 자신의 부모(추천인)에게 판매 이익의 10%를 전달한다.
 2. 이익을 받은 부모는 또 자신의 부모에게 받은 이익의 10%를 전달한다.

- 이를 부모가 center인 사원일 때까지 반복한다. 

 

코드

import java.util.HashMap;

class Solution {
	
    // 사원 정보를 저장할 클래스 (번호, 이름, 이익)
	static class Employee{
		String name;
		int num;
		int result;
		public Employee(String name, int num) {
			super();
			this.name = name;
			this.num = num;
			this.result = 0;
		}
	}
	
	static public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int[] answer = {};
        int employeeCnt = enroll.length;
        int[] parent = new int[employeeCnt+1];
        
        HashMap<String, Integer> map = new HashMap<>();		// 사원이름-번호 저장
        Employee[] emp = new  Employee[employeeCnt+1];
        for(int i = 1; i<=employeeCnt;i++) {
        	emp[i] = new Employee(enroll[i-1], i);
        	map.put(enroll[i-1], i);
        }
        
        for(int i = 1; i<=employeeCnt;i++) {
        	String parentName = referral[i-1];	// 부모 이름에 대응하는 번호
        	if(parentName.equals("-")) {	// 부모가 민호(center)라는 뜻
        		parent[i] = 0;
        	} else {	
        		int parentNum = map.get(parentName);
        		parent[i] = parentNum;
        	}
        }
        
        // 판매 내역
        for(int i = 0, len = seller.length;i<len;i++) {
        	String sellerName = seller[i];	// 판매자 이름
        	int sellCnt = amount[i];		// 판매자가 판 칫솔의 개수
        	int money = sellCnt * 100;		// 판매자가 얻은 원래 이익
        	int sellerNum = map.get(sellerName);	// 판매자에게 할당된 사원번호
        	int index = sellerNum;	// 부모 찾아갈 index

            while(true) {
            	// 자신의 추천인이 센터인 사원까지 쭉 가줘야 한다!
            	if(parent[index] == 0) {	
            		emp[index].result += money - (int)(money*0.1);
            		break;
            	}
                // 자신의 이익에서 10% 제한 금액 : 진정한 이익  
           		emp[index].result += money - (int)(money*0.1);	        		
      			index = parent[index];
           		money = (int)(money*0.1);	// 부모에게 10%의 이익 넘겨줌
           	}
        }
        
        answer = new int[employeeCnt];
        for(int i = 1; i<=employeeCnt;i++) {
        	answer[i-1] = emp[i].result;
        }
        return answer;
    }
}

 

 굉장한 시간으로 통과하게 된다.😓