다단계 칫솔 판매

사용 알고리즘: dfs

사용 언어: java

 

import java.io.*;
import java.util.*;

class Solution {
    static HashMap<String, Integer> nameAndNumber = new HashMap<>();
    static ArrayList<Integer>[] parent;
    static int[] answer2;
    
    public int[] solution(String[] enroll, //등록된 사람
                          String[] referral, //추천인 -> 리스트...?
                          String[] seller, //판매 성공한 사람
                          int[] amount //몇 개 성공?
                         ) 
    {
        //메인
        int employeeCnt = enroll.length;
        nameAndNumber.put("-", 0);
        for(int i=0; i<employeeCnt; i++) {
            nameAndNumber.put(enroll[i], i+1);
        }
        // System.out.println(nameAndNumber);
        
        
        parent = new ArrayList[employeeCnt+1]; //윗선 저장(0은 center)
        for(int i=0; i<employeeCnt+1; i++) {
            parent[i] = new ArrayList<>();
        }
        for(int i=0; i<employeeCnt; i++) {
            int parentNumber = nameAndNumber.get(referral[i]);
            parent[i+1].add(parentNumber);
        }
        // for(ArrayList<Integer> al : parent) {
        //     System.out.println(al);
        // }
        
        answer2 = new int[employeeCnt+1];
        
        for(int i=0; i<seller.length; i++) {
            int initPrice = 100 * amount[i];
            dadangye(initPrice, nameAndNumber.get(seller[i]) );
            // System.out.println(Arrays.toString(answer2));
        }
        
        int[] answer = new int[employeeCnt];
        for(int i=0; i<employeeCnt; i++) {
            answer[i] = answer2[i+1];
        }
        
        return answer;
        //메인-
    }
    
    
    private static void dadangye(int curPrice, int curNumber) {
        if(curPrice == 0 || curNumber == 0) {
            return;
        }
        
        int parentNumber = parent[curNumber].get(0);
        int goUpMoney = curPrice / 10;
        answer2[curNumber] += curPrice - goUpMoney;
        
        dadangye(goUpMoney, parentNumber);
    }
    
}

 

map을 잘 쓰면 좋다.

 

 

면접 기다리는 시간에 두 문제 읽고 종이에다가 풀이 방법을 끄적여 놨다. 

그 논리를 그대로 코드로 옮기니까 둘 다 금방 풀렸다!

설계 중요!