[프로그래머스](Java) - 다단계 칫솔 판매

문제 링크

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

문제 풀이

dev매칭 백엔드 부분을 할때 시간초과가 나서 풀지 못했던 문제였다. 마지막 11,12,13에서 시간초과가 났으며 결국 해결하지 못했다.
결국 이번에는 다시 풀어도 시간 초과는 해결하지 못했고 다시 문제를 보다가 dfs의 종료조건에 넘겨주는 금액이 0인경우에도 반복을 종료하는 조건을 추가했고, 바로 정답을 맞출 수 있었다. 무의미한 반복... 멈춰!

map이라는 Map에는 <사람이름, 총금액> , connect라는 Map에는 <사람이름, 자신 바로 위에 연결된 사람>을 담고 있도록 설게했다.

static Map<String,Integer> map = new HashMap();
static Map<String,String> connect = new HashMap();

for(int i=0; i<enroll.length; i++){
    map.put(enroll[i],0);
    connect.put(enroll[i],referral[i]);
}

seller와, seller가 판매한 칫솔*100을 넘겨주며
맨 마지막 사람이 없는경우 referral이"-" 경우나, 넘겨주는 금액이 0인 경우에는 바로 해당 반복을 종료시켰다.
이 부분을 반복문이 아닌 재귀를 통해서 처리해도 될것이라 판단해서 재귀로 구현하였다.
판매금액의 0.9를 자신이 가지는데 소숫점을 올림해서 처리하므로 Math.ceil을 사용
replace를 통해서 기존에 가지고 있던 금액에 판매금액의 0.9를 한 가격을 더해줘서 값을 갱신해주었고 connect를 통해서 다음 사람을 확인하여 나머지 금액과 함께 넘겨주었다.

    public static void dfs(String name, int money){

        if(name.equals("-") || money ==0){
            return;
        }

        int mainmoney = (int)(Math.ceil(money * 0.9));
        int restmoney = money-mainmoney;
        String next = connect.get(name);
        map.replace(name,map.get(name)+mainmoney);
        dfs(next,restmoney);

    }

결과값은 enroll순서대로 들어가야하므로 map.get(enroll[i])를 통해서 해결했다.

        for(int i=0; i<enroll.length; i++){
            answer[i] = map.get(enroll[i]);
        }

코드

import java.util.*;

class Solution {
    
    static Map<String,Integer> map = new HashMap();
    static Map<String,String> connect = new HashMap();
    
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int[] answer = new int[enroll.length];
        
        for(int i=0; i<enroll.length; i++){
            map.put(enroll[i],0);
            connect.put(enroll[i],referral[i]);
        }
        
        for(int i=0; i<seller.length; i++){
            dfs(seller[i],amount[i]*100);
        }
        
        for(int i=0; i<enroll.length; i++){
            answer[i] = map.get(enroll[i]);
        }
        
        
        return answer;
    }
    
    public static void dfs(String name, int money){
        
        if(name.equals("-") || money ==0){
            return;
        }
        
        int mainmoney = (int)(Math.ceil(money * 0.9));
        int restmoney = money-mainmoney;
        String next = connect.get(name);
        map.replace(name,map.get(name)+mainmoney);
        dfs(next,restmoney);

    }
}