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

1. 문제

프로그래머스

 

---

2. 풀이 과정

---

일단 문제를 풀기에 앞서 몇가지 주의사항을 생각해봤다.

1. center의 수익은 계산하지 않는다.

2. 자신의 추천인에게 수익금의 10%를 주고 그 추천인의 추천인에게도 10%를 준다.(없을 때까지)

3. 10% 한 값이 소수면 소수부분을 버리고 추천인에게 준다.

4. 10%가 1보다 작으면 분배하지 않는다.

 

그리고 이 문제를 풀기위해 두 가지 해시맵을 생각했다.

1. 판매원 - 추천인 해시맵

2. 판매원 - 수익 해시맵

 

일단 해시맵을 사용한 까닭은 조회를 O(1)로 할 수 있기 때문이다. 

이 문제의 입력 최대 크기를 보면 seller가 100,000, enroll이 10,000이다.

그렇다는 것은 시간복잡도에 주의해야한다는 의미이다. 그렇기 때문에 조회를 가장 효율적으로 할 수 있는 해시맵을 사용했다.

 

또한 1. 판매원 - 추천인 관계로 해시맵을 사용한 이유는 이 문제에선 자신의 추천인 뿐만 아니라 추천인의 추천인들까지 고려를 해야한다. 이러한 추천인 체인구조를 참조하기 좋은 구조라고 생각했기 때문에 해시맵을 사용했다.

 

2. 판매원 - 수익 해시맵은 각 판매원의 총 수익을 계산하기 위한 해시맵이다. 배열에 이 정보를 저장하게 된다면 해당 판매원을 찾기위한 O(N) 연산을 해야하기 때문에 시간초과가 뜰 수 있다. 그렇기에 해시맵을 사용했다.

 

문제를 풀기위한 기본 재료들은 모두 준비가 되었다.

이제 seller 배열과 amount배열을 돌며 각 seller와 그 seller의 추천인들의 수익을 계산해주면 된다.

 

다음을 보자

1. Young - 1200원

• Young은 1200원의 90%인 1080원을 수익으로 받는다.
• 나머지 10%는 Young의 추천인인 Edward와 Edward의 추천인들에게 간다.

• Edward는 120원의 90%인 108원을 수익으로 받는다.
• 나머지 10%는 Edward의 추천인인 Mary와 Mary의 추천인들에게 간다.

• Mary는 12원의 90%인 11원을 수익으로 받는다.(10.8원 인데 위의 주의사항 3번에 의해 11원이 됨)
• 나머지 10%는 Mary의 추천인인 Center에게 간다.
• Center는 계산할 필요없으니 수익 분배 끝

2. John - 400원

• John는 400원의 90%인 360원을 수익으로 받는다.
• 나머지 10%는 John의 추천인인 Center에게 간다.
• Center는 계산할 필요없으니 수익 분배 끝

3. Tod - 200원

• Tod는 200원의 90%인 180원을 수익으로 받는다.
• 나머지 10%는 Tod의 추천인인 Jamie와 Jamie의 추천인들에게 간다.

• Jamie는 20원의 90%인 18원을 수익으로 받는다.
• 나머지 10%는 Jamie의 추천인인 Mary와 Mary의 추천인들에게 간다.

• Mary는 2원의 90%인 2원을 수익으로 받는다.(1.8원인데 위의 주의사항 3번에 의해 2원이 됨)
• 나머지 10%는 John의 추천인인 Center에게 간다.
• 하지만 나머지가 0원이므로 계산 끝

4. 나머지

나머지 seller들에 대해서도 같은 과정을 거치면 최종 결과를 다음과 같다.

 

이제 코드로 보자

3. 내 코드

---

import java.util.*;
class Solution {
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        HashMap<String, String> who_is_ref = new HashMap<>();
        HashMap<String, Integer> sell_amt = new HashMap<>();
        
        // 판매원 별 추천인 정보 해시맵에 저장
        for(int i = 0; i < enroll.length; i++) {
            who_is_ref.put(enroll[i], referral[i]);
        }
    
        // 판매원 별 판매 수익 정보 초기화
        for(int i = 0; i < enroll.length; i++) {
            sell_amt.put(enroll[i], 0);
        }
    
        
        // 판매원의 판매정보를 보고 수익 배분하기
        for(int i = 0; i < seller.length; i++) {
            String seller_name = seller[i];
            int total_profit = amount[i] * 100;
            
            // 판매원 및 추천인이 받는 수익 계산하기
            while(!seller_name.equals("-") && total_profit > 0) {
                // 10%를 계산할 때는 원단위에서 절사함(ex: 12원이면 1원만 가져감)
                int my_profit = (int)Math.ceil(total_profit * 0.9); 
                total_profit = (int)Math.floor(total_profit * 0.1);
                
                sell_amt.put(seller_name, sell_amt.get(seller_name) + my_profit);
                
                
                // 판매원 재설정
                seller_name = who_is_ref.get(seller_name);
            }
        }
        
        int[] answer = new int[enroll.length];
        
        for(int i = 0; i < enroll.length; i++){
            String seller_name = enroll[i];
            answer[i] = sell_amt.get(seller_name);
        }
        return answer;
        
    }
}

시간 복잡도

• O(k*m)
  • k: 판매원(seller)의 수
  • m: 추천인(referral)의 체인 수(seller의 판매원을 기준으로 몇번 위로 올라갔는지)

해시맵을 통해서 조회 연산의 시간복잡도를 줄이고 체인을 통해 추천인을 찾았기 때문에 최종 시간복잡도를 줄일 수 있었다.

4. 피드백

---

• 조회를 빠르게 할 땐 해시맵을 사용하자