[Programmers/Java] Lv3. 다단계 칫솔 판매

import java.util.*;

class Solution {
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int N = enroll.length;
        int[] answer = new int[N];

        HashMap<String, String> adj = new HashMap<>(); // 인접한 관계를 저장       
        HashMap<String, Integer> idx = new HashMap<>(); // 각 사람별 enroll idx 저장
        for (int i=0; i<N; i++) {
            String boss = referral[i];
            String me = enroll[i];
            if (adj.get(me) == null) {
                adj.put(me, boss);
                idx.put(me, i);
           }
        }

        int sellN = seller.length;
        for (int i=0; i<sellN; i++) {
            // 지금 현재 기준이 되는 사람
            int currentIdx = idx.get(seller[i]);
            String currentPerson = seller[i];
            int currentMoney = amount[i] * 100;

            // 기준인의 상사가 센터가 아닐 때까지 반복
            while (!adj.get(currentPerson).equals("-")) {

                // 현재 남은 돈이 0원이라면 분배할 필요 X
                if (currentMoney == 0) {
                    break;
                }

                // 기준인의 상사
                String currentBoss = adj.get(currentPerson);
                int bossIdx = idx.get(currentBoss);
                int bossMoney = currentMoney / 10;

                // 기준인의 잔고에 더해줌 (상사에게 줄 것 빼서)
                answer[currentIdx] += currentMoney - bossMoney;

                // 이제는 상사가 기준인이 됨
                currentIdx = bossIdx;
                currentMoney = bossMoney;
                currentPerson = currentBoss;
            }
            // 맨 마지막 (상사가 센터일경우)
            int lastMoney = currentMoney / 10;
            // 10% 떼어주고 남은돈 가짐
            answer[currentIdx] += currentMoney - lastMoney;
        }

        return answer;
    }
}

 

1. 다단계(?) 회사의 직원들을 전부 순회하면서 인덱스와, 해당 직원의 상사(?) 를 hashmap 으로 저장해두었다.

2. 내 상사가 센터 (-) 가 아닐 때 까지 while 문으로 타고 타고 올라가서 돈을 배분했다.

3. 상사가 센터(루트노드) 일 경우 while 문 종료

4. 센터에 10% 떼주고 남은 돈을 가짐

5. 다음 판매로 이동!

 

=> 마지막 테케 3개정도가 시간 초과가 났는데, 이미 배분금이 0원인데도 계속해서 타고 올라가는 경우가 발생해서 그랬던 것이었다. currentMoney 가 0원일 때 종료하라는 종료 조건을 걸어주니 시간초과 없이 통과 됐다!

 

 

아직 자바가 익숙하지 않아서 IDE 없이 기억을 더듬어가며 메서드 명을 찾느라 힘들었다

코테보려면 IDE 없이 알고리즘 푸는 거에 익숙해져야겠다