[알고리즘] 프로그래머스 다단계 칫솔 판매 Java(자바)

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

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

 

 

dev-matching 인가에 출제 되었던 문제이다. 당시 문제를 푼줄 알았지만 당시 코드로 실행해보니 테스트케이스13에서 부터 시간초과가 뜨더라 그래서 다시 풀어봤다.

 

<코드 설명>

이름 별로 index를 지정해주고 이를 해시맵에 저장한다.

또한 이름 별로 Seller 객체를 생성해서 최종적으로 부모가 누구인지 명시한다.

 

이를 통해 부모가 없을경우("-")까지 이익을 전달해주는 재귀문구조로 코드를 작성하였다.

 

import java.util.*;

class Solution {
    static int[] answer;
    static HashMap<String, Integer> hmap;
    static Seller[] sellers;
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount)
    {
        answer = new int[enroll.length];
        hmap = new HashMap<String, Integer>(); //이름 , 해당 이름의 index
        sellers = new Seller[enroll.length]; // enroll을 순서대로 저장할 공간
        
        int idx = 0;
        for(String name : enroll){
            hmap.put(name,idx);
            sellers[idx++] = new Seller(name);
        }
        
        //부모를 추가해준다.
        idx = 0;
        for(String parent : referral){
            sellers[idx++].parent = parent;
        }
        
        int len = seller.length;
        for(int i=0; i<len; i++){
            double profit = 0;
            
            idx = hmap.getOrDefault(seller[i],0);
            answer[idx] += (int)((100* amount[i]) * 0.9);
            profit = (100 * amount[i]) * 0.1;
            
            if(sellers[idx].parent.equals("-") == false){
                send_profit(sellers[idx].parent,(int)profit);    
            }
        }
        return answer;
    }
    //부모가 없을 때 까지
    static void send_profit(String name, double profit){
        int idx = hmap.getOrDefault(name,-1);
        //부모가 없을 조건
        if(idx == -1) return;

        if(profit < 10){
            answer[idx] += (int)profit;    
        }
        else{
            answer[idx] += profit - (int)(profit * 0.1);
            profit = (int)(profit * 0.1);
            send_profit(sellers[idx].parent, profit);
        }
    }
}

class Seller
{
    public String name;
    public String parent;
    public Seller(String name){this.name = name;}
}

 

<결과>