2021 Dev-Matching: 웹 백엔드 개발자(상반기) - 다단계 칫솔 판매

문제 유형

• 구현

문제 접근

• 답
  • 각 인원이 가지는 돈
• 주어지는 정보
  • 인원 100,000
  • 자식, 부모 관계
  • 소득이 발생하는 대상
• 후보
  • 완전탐색
    • 부적합
      • 분기점에 따른 경우의 수가 나눠지지 않기 때문에 부적합
  • 구현
    • 적합
      • n*n = 1억 연산
      • (전체 인원) * (각 인원으로 인해 발생하는 최대 연산량)
      • ⇒ 문제에서 주어지는 설명을 그대로 따라해서 코드를 구성해도 연산량 초과X
• 전체 코드

import java.util.*;

class Node{
    public String parent;
    public String name;
    public int value;
    
    public Node(String parent, String name){
        this.parent = parent;
        this.name = name;
        this.value = 0;
    }
}

class Solution {
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int[] answer = {};
        int n = enroll.length;
        
        Map<String, Node> map = new HashMap<>();
        
        for(int i = 0; i<n; i++){
            String parent = referral[i];
            String child = enroll[i];
            map.put(child, new Node(parent, child));
        }
        
        int brush = 100;
        for(int i = 0; i<seller.length; i++){
            String name = seller[i];
            int value = amount[i] * brush;
            
            map.get(name).value += value;
            while(value/10 >= 1){
                value /= 10;
                map.get(name).value -= value;
                
                String parent = map.get(name).parent;
                if(parent.equals("-")){
                    break;
                }

                map.get(parent).value += value;
                
                name = parent;
            }
        }
        
        int[] values = new int[n];
        for(int i = 0; i<n; i++){
            String name = enroll[i];
            values[i] = map.get(name).value;
        }
    
        return values;
    }
}