2021 Dev-Matching 웹 백엔드 개발자 (상반기)
https://programmers.co.kr/learn/courses/30/lessons/77486

🥚문제

---

🥚입력/출력

---

🧂아이디어

• 지문 내 예시 이미지에만 눈길이 갔었는데, 입출력 조건까지 꼼꼼하게 읽고 나서야 풀어낼 수 있었던 문제
• 생각보다 어렵지 않은 문제였음! 👀 역시 PS를 할 때는 특정 생각(맞는데왜틀려요)에 사로잡히지 않도록 하는 게 중요한 것 같다...
  

[시간초과 해결법]
이렇게 테스트케이스 중 시간 초과가 뜨는 것을 해결한 방법은,
distributeBenefit함수에서 while loop를 돌 때, new_benefit이 0이 되면 break를 걸어주는 것!
benefit이 0이면 사실상 분배할 이익이 없는 상태이기 때문에 루프를 중단해도 된다. 이처럼 불필요한 실행을 줄여주는 것이 중요하다!

---

🍳코드

import java.util.ArrayList;

class Solution {
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        // 직원의 정보를 담고 있는 Node data type 기반의 arraylist 생성
        ArrayList<Node> sellers = constructSellers(enroll, referral);
        
        // seller, amount 순회하면서 benefit 배분
        for(int i = 0; i < seller.length; i++){
            distributeBenefit(seller[i], amount[i], sellers);
        }
        
        // 리턴값 구성
        int[] answer = new int[sellers.size()];
        for(int i = 0; i < sellers.size(); i++){
            answer[i] = sellers.get(i).benefit;
        }
        return answer;
    }
    
    private static ArrayList<Node> constructSellers(String[] enroll, String[] referral){
        ArrayList<Node> sellers = new ArrayList<>();
        
        for(int i = 0; i < enroll.length; i ++){
            String name = enroll[i];
            String parent_name = referral[i];
            // parent_name을 가지고 있는 Node를 찾는다
            Node parent = null;
            if(!parent_name.equals("-")){
                for(int j = 0; j < sellers.size(); j ++){
                    if(sellers.get(j).name.equals(parent_name)){
                        parent = sellers.get(j);
                        break;
                    }
                }
            }
            Node newSeller = new Node(name, parent);
            newSeller.parent = parent;
            sellers.add(newSeller);
            
        }
        
        return sellers;
    }
    
    private void distributeBenefit(String seller_name, int amount, ArrayList<Node> sellers){
        Node seller = null;
        // seller_name을 가지는 Node를 찾음
        for(int i = 0; i < sellers.size(); i++){
            Node someone = sellers.get(i);
            if(someone.name.equals(seller_name)){
                seller = someone; // seller 설정
                break;
            }
        }
        
        // 새로 추가된 benefit 기반으로 이익 배분
        int new_benefit = amount * 100;
        Node target = seller;
        // target이 null이 아닐 때까지 계속 위로 올라감
        while(target != null){
            int benefit_10 = (int)(new_benefit * 0.1 ); // 10%
            target.benefit += (new_benefit - benefit_10); // target의 benefit 재설정
            
            target = target.parent; // target을 parent로 변경
            new_benefit = benefit_10; // new_benefit을 benefit_10으로 변경
            
            // ⭐ new_benefit이 0이면 while문 중단해야 시간초과 뜨지 않음!
            // 아무 일도 일어나지 않는 반복은 낭비
            if(new_benefit == 0)
                break;
        }
    }
}

class Node{
    String name;
    int benefit;
    Node parent;
    
    public Node(String name, Node parent){
        this.name = name;
        benefit = 0;
    }
    
    public String toString(){
        if(parent == null)
            return "[" + name + "] $" + benefit + ", no parent";
        return "[" + name + "] $" + benefit + ", parent: " + parent.name;
    }
}

---

🍵부록

(나의 반성을 위한 😅)

[테케는 통과하지만 제출시 통과하지 못하는 코드 🔽]

• 트리 형태로 자료구조를 만들어보고자 했음
• 문제를 꼼꼼히 읽지 않고 코딩부터 한 안좋은 예시...
  - 부모 노드로 가면서 이익이 배분되는 방식을 숙지하지 못함
  - seller에 중복된 이름이 등장할 수 있다는 조건을 이해하지 못함

import java.util.ArrayList;

class Solution {
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        // 트리 구조 생성
        ArrayList<Node> Tree = new ArrayList<>();
        Node root = new Node("root"); // 루트 노드 생성
        root.setLevel(0);
        Tree.add(root);// 루트 노드 트리에 삽입
        
        // enroll, referral 순회하며 노드 추가
        for(int i = 0; i < enroll.length; i++){
            String name = enroll[i];
            // 노드 생성
            Node currentNode = new Node(name);
            
            // 추천인 구하기
            String ref = referral[i];
            // 어느 누구의 추천도 없이 조직에 참여한 사람
            if(ref.equals("-")){
                Tree.add(currentNode); // 트리 자료구조에 추가
                currentNode.setParent(root); // 현재 노드의 parent를 root로 추가
                currentNode.setLevel(1);// 노드의 level을 1로 설정
                root.addChildNode(currentNode);// root의 children에 current Node 추가
            }
            // 누군가의 추천으로 조직에 참여한 사람
            else{
                // Tree를 순회하면서 추천인의 Node를 찾아냄
                for(int j = 0; j < Tree.size(); j++){
                    // Tree에서 i번째 Node의 name이 ref의 추천인과 같다면
                    if(Tree.get(j).getName().equals(ref)){
                        Tree.add(currentNode); // 트리 자료구조에 추가
                        currentNode.setParent(Tree.get(j));// 현재 노드의 parent를 root로 추가
                        currentNode.setLevel(Tree.get(j).getLevel() + 1);// 노드의 level을 parent의 level + 1로 설정
                        Tree.get(j).addChildNode(currentNode);// parent의 children에 현재 노드 추가
                    }
                }
            }
        } // 노드 추가 완료
        
        
        // seller, amount 순회하며 판매액 추가
        for(int i = 0; i < seller.length; i++){
            String name = seller[i];
            int sales = amount[i] * 100;
            
            for(int j = 0; j < Tree.size(); j++){
                if(Tree.get(j).getName().equals(name)){
                    // seller에는 같은 이름이 중복해서 들어있을 수 있기 때문에
                    // setSales할 때, 이전 값이 있다면 그것에 추가해서 set하도록
                    Tree.get(j).setSales(Tree.get(j).getSales() + sales);
                    break;
                }
            }
        }
        
        // Tree print
        //show(Tree);
        totalBenefit(Tree);
        //System.out.println("수익 배분 후");
        //show(Tree);
        
        // enroll에 명시된 이름에 맞춰 결과값 구성
        int[] answer = new int[enroll.length];
        for(int i = 0; i < enroll.length; i++){
            String name = enroll[i];
            
            for(int j = 0; j < Tree.size(); j++){
                if(Tree.get(j).getName().equals(name)){
                    answer[i] = Tree.get(j).getSales();
                    break;
                }
            }
        }
        return answer;
    }
    
    public static void show(ArrayList<Node> Tree){
        for(int i = 0; i < Tree.size(); i++){
            System.out.println(i + " " + Tree.get(i));
        }
    }
    
    public static void totalBenefit(ArrayList<Node> Tree){
        
        int max_level = 0;
        for(Node currentNode : Tree){
            if(max_level < currentNode.getLevel())
                max_level = currentNode.getLevel();
        }
        
        // level의 크기가 큰것부터 이익을 배분해야 잘 배분할 수 있음!
        while(max_level > 0){
            for(Node currentNode : Tree){
                // 탐색 노드의 level이 max_level이면
                if(currentNode.getLevel() == max_level){
                    // 10%를 parent에게 전달
                    int benefit = (int)(currentNode.getSales() * 0.1);
                    if(benefit > 0){
                        Node parentNode = currentNode.getParent();
                        parentNode.setSales(parentNode.getSales() + benefit);
                        currentNode.setSales(currentNode.getSales() - benefit);
                    }
                }
            }
            max_level--;
        }
    }
}

class Node{
    private String name;
    private Node parent;
    private int sales;
    private int level;
    private ArrayList<Node> children = new ArrayList<>();
    
    public Node(String name){
        this.name = name;
    }
    
    public void addChildNode(Node child){
        children.add(child);
    }
    
    public void setParent(Node node){
        parent = node;
    }
    
    public void setLevel(int level){
        this.level = level;
    }
    
    public void setSales(int sales){
        this.sales = sales;
    }
    
    public String getName(){
        return name;
    }
    
    public int getSales(){
        return sales;
    }
    
    public int getLevel(){
        return level;
    }
    
    public Node getParent(){
        return parent;
    }
    
    public String toString(){
        String result = "[" + name + "](level" + level + ") $" + sales + ": ";
        if(children.size() > 0){
            for(int i = 0; i < children.size(); i++){
                result += children.get(i).getName() + " ";
            }
        }
        
        return result;
    }
}