[카카오 기출 문제]다단계 칫솔 판매- 레벨 3, 링크드리스트 + 트리 + 노드

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

프로그래머스

 

이번 문제는 링크드리스트를 활용하여 트리를 만들어 계산을 하면되는 문제입니다.

 

기억해야할점들

 

첫번째. 이 문제 같은경우 child에서 parent로 올라가는 경우만 고려합니다.

문제를 보면 child에서 어떤 물건을 구매하고 하나씩 prev를 거쳐가며 parent까지 가는 방식으로 양방향 노드를 사용할 필요가 없습니다.

 

두번째, 각 노드의 객체정보를 알기 위하여 HashMap을 사용하여 편하게 알아냅니다.

 

세번째, Calculate(int amount) 함수에서 amount < 10 인경우(원 단위에서 절사하는 경우)를 갈라주면 최대 10배이상 빨라집니다.

 

코드입니다.

class Solution {
    public Node center = new Node("-");
    public HashMap<String, Node> hashmap = new HashMap<String, Node>();
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int[] answer = new int[enroll.length];
        
        //각 노드들의 위치를 쉽게 연결하기 위하여 HashMap을 통해서 관리합니다.
        hashmap.put("-", center);
        
        //각 판매원의 이름을 담은 배열 enroll을 통하여, referall과 함꼐 Parent를 연결시킵니다.
        for(int i=0;i<enroll.length;i++){
            String enrolltemp = enroll[i];
            String referraltemp = referral[i];
            
            //판매원의 이름으로 node를 생성
            Node node = new Node(enrolltemp);
            hashmap.put(enrolltemp, node);
            
            //판매원을 다단계 조직에 참여시킨 다른 판매원의 이름, node의 parent로 넣습니다.
            //굳이 양방향으로 할필요 없으므로 자식에서 prev만 연결시킵니다.
            //항상 parent가 먼저 입력되므로 hashmap.get을 사용하면 바로 알수 있습니다.
            Node prev = (Node) hashmap.get(referraltemp);
            node.prev = prev;
            
        }
        
        for(int i=0;i<seller.length;i++){
            String sellertemp = seller[i];
            int amounttemp = amount[i]*100;
            
            Node sellernode = hashmap.get(sellertemp);
            
            sellernode.calculate(amounttemp);
 
        }
        
        
        for(int i=0;i<enroll.length;i++){
            answer[i] = hashmap.get(enroll[i]).money;
        }
        
        // for(Entry <String, Node> entrySet : hashmap.entrySet()){
        //     System.out.println(" "+entrySet.getKey() +  " "+entrySet.getValue().name);
        // }
        
        return answer;
    }
}
 
class Node{
    String name=null;
    Node prev;
    int money=0;
    public Node(){
        
    }
    public Node(String name){
        this.name = name;
    }
    
    public void calculate(int amount){
        
        //재귀를 사용
        int moneytoParent = amount / 10;
        this.money += amount - moneytoParent;
        if(this.prev != null)
            this.prev.calculate(moneytoParent);
   
 
        //일반 코드
//         Node now = this;
//         while(now != null){
//             int moneytoParent = amount / 10;
//             if(amount < 10){
//                 now.money += amount;
//                 return ;
//             }
//             now.money += amount - moneytoParent;
//             amount = moneytoParent;
//             now = now.prev;
            
//             if(now.prev == null){
//                 return ;
//             }
            
 
//         }
   
        //가장  빠른 코드, if amount < 10 이면 바로끝내서 제일 빠른듯합니다.
//         Node now = this;
//         while(now != null){
 
//             if(amount < 10){
//                 now.money += amount;
//                 return ;
//             }
//             int movemoney = amount/10;
//             amount -= amount / 10;
//             now.money += amount;
//             amount = movemoney;
 
//             now = now.prev;
 
//             if(now.prev == null){
//                 return ;
//             }
 
 
//         }
        
        return ;
        
        
        
    }
}

 

HashMap으로 푼경우, 조회가 훨씬 빠르기에 속도가 현저히 줄어듭니다. 

import java.util.Map.*;
import java.util.*;
class Solution {
       
    HashMap<String, Node> hashmap=  new HashMap<String, Node>();
    Node root = new Node();
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int[] answer = {};
        
        for(int i=0;i<enroll.length;i++){
            Node temp = new Node();
            hashmap.put(enroll[i], temp);
        }
        
        for(int i=0;i<referral.length;i++){
            String parent = referral[i];
            if(parent.equals("-")){
                Node temp = hashmap.get(enroll[i]);
                temp.parent = root;
            }
            else{
                Node temp = hashmap.get(enroll[i]);
                temp.parent = hashmap.get(parent);
            }
        }
        for(int i=0;i<seller.length;i++){
            String seller_value = seller[i];
            int money = amount[i] * 100;
            
            Node temp = hashmap.get(seller_value);
            while(true){
                
                if(money < 10 || temp == root){
                    temp.money += money;
                    break;
                }
                int distributemoney = (int)Math.ceil(money * 0.9);
                temp.money += distributemoney;
                money = money - distributemoney;
                
                if(temp == root)
                    break;
                temp = temp.parent;
                
                
            }
            
        }
        
        answer = new int[enroll.length];
        for(int i=0;i<answer.length;i++){
            answer[i] = hashmap.get(enroll[i]).money;
        }
        // System.out.print(root.money);
        // for (Entry<String, Node> entry : hashmap.entrySet()) {
        //     System.out.print("[key]:" + entry.getKey() + ", [value]:" + entry.getValue().money);
        // }
        
        
        return answer;
    }
    
    class Node{
        Node parent =null;
        int money = 0;
        public Node(){
            
        }
    }
}

 

새로 풀어봤을떄, HashMap으로 풀려했지만, 더빠르게 풀기위해 ArrayList로 바로 풀어봤습니다.

import java.util.*;
class Solution {
    ArrayList<Node> graph = new ArrayList<Node>();
    Node root = new Node();
    
    int[] answer = {};
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        root.name="-";    
        
        for(int i=0;i<enroll.length;i++){
            String name = enroll[i];
            Node temp = new Node();
            temp.name = name;
            graph.add(temp);
        }
        
        
        for(int i=0; i<referral.length;i++){
            String referral_name = referral[i];
            
            if(referral_name.equals("-")){
                graph.get(i).parent = root;    
            }else{
                for(int j=0;j<graph.size();j++){
                    if(referral_name.equals(graph.get(j).name)){
                        graph.get(i).parent = graph.get(j);        
                    }
                }
            }
        }
 
        
        for(int i=0;i<seller.length;i++){
            String name = seller[i];
            int count = amount[i] * 100;
            
            for(int j=0;j<graph.size();j++){
                
                if(name.equals(graph.get(j).name)){
                    Node temp = graph.get(j);
                    
                    while(true){
                        
                        if(count < 10 || temp == root){
                            temp.money += count;
                            break;
                        }
                        int distribute = (int)Math.ceil(count * 0.9);
                        temp.money += distribute;
                        count = count - distribute;
                        temp = temp.parent;
                        
                    }       
                }
            }
            
        }
            System.out.print("root:"+root.money);
    for(int k=0;k<graph.size();k++){
        System.out.print(" "+graph.get(k).money);
    }
    System.out.println();
                        
        // System.out.println(root.money);
        answer = new int[graph.size()];
        for(int i=0;i<graph.size();i++){
            answer[i] = graph.get(i).money;
        }
        
        return answer;
    }
    
    class Node{
        String name;
        Node parent=null;
        int money = 0;
        public Node(){
            
        }
    }
}