[2021 Dev-Matching: 웹 백엔드 개발자(상반기)][구현/Map 활용] 다단계 칫솔 판매 - Java

문제 바로가기

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

 

이 문제 역시 올해 상반기 데브 매칭 문제입니다.

레벨 3이라는데 3까진 절대 아닌거 같고.. 암튼 걍 시키는 대로 말 잘 들으면 맞출 수 있습니다.

 

import java.util.*;

class Solution {        
    Map<String, Integer> result = new HashMap<>();
    Map<String, String> refer = new HashMap<>();

    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        
        for (int i = 0; i < enroll.length; i++) {
            refer.put(enroll[i], referral[i]);
            result.put(enroll[i], 0);
        }
        
        for (int i = 0; i < seller.length; i++) {
            distribute(seller[i], amount[i]);
        }
        
        int[] answer = new int [enroll.length];
        
        for(int i = 0; i < enroll.length; i++) {
            answer[i] = result.get(enroll[i]);
        }
        
        return answer;
    }
    
    void distribute(String seller, int amount) {
        int now = amount * 100;
        
        while(true) {
            String upper = refer.get(seller);
            int upCost = (int) (now * 0.1);
            int mine = now - upCost;
            
            result.put(seller, result.get(seller) + mine);
            
            now = upCost;
            
            if (upper.equals("-") || upCost == 0) return;
            seller = upper;
        }
    }
}

 

기본적으로 배열로 들어온 인풋을 Map으로 바꿔서 문제를 풀었습니다.

수익을 분배하는 distribute() 메서드에서 위로 쭉쭉 올라가면서 계산해서 각자의 수익을 구해서 더해줍니다.

문제에서 보면 자료구조 형태가 트리 구조긴 한데, 부모는 하나고 위로 올라가면서 문제를 풀기 때문에 저렇게 반복문으로 슥슥 올라가주면 됩니다.

 

참고로 맨처음 제출했을때 테케 몇개가 시간초과가 떴씁니다. 

당연히 무한 반복문 while(true) 쪽이 문제였는데요, 추천인에게 떨어지는 이익금(upCost)가 0이 된다면 위로 올라가봤자 어차피 다 0원이기 때문에 이때 반복문을 멈춰주면 시간초과가 해결된답니다.

 

감사합니다!!