다단계 칫솔 판매 Java

프로그래머스

package 프로그래머스.자바.다단계칫솔판매;import java.util.*;
class Solution {
    // 이름과 번호가 키 쌍으로 들어감.
    Map<String, Integer> map = new HashMap<>();
    int[] arr;

    void dfs(int x, int money, int[] answer){
        int giveMoney = (int)(money*0.1);
        int myMoney = money - giveMoney;

        answer[x] += myMoney;

        if(arr[x] == -1) return;
        dfs(arr[x], giveMoney, answer);
    }

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

        Arrays.fill(arr, -1);
        // 1. 이름을 통해 enroll배열에서 해당 이름 인덱스를 바로 얻을 수 있도록 Map에 저장
        // 2. reffreal을 사용하여 그래프 간선 추가
        // 3. arr 초기화
        for(int i = 0; i < enroll.length; i++){
            String s = referral[i];
            map.put(enroll[i], i);
            if(!s.equals("-")) arr[i] = map.get(s);
        } // -> <john, 0> <mary, 1> ...

        // 4. 각 판매마다 이익 갱신
        for(int i = 0; i < seller.length; i++){
            dfs(map.get(seller[i]), amount[i]*100, answer);
        }

        return answer;
    }
}

 

 

쉽게 풀줄 알았지만. . 시간 초과로 늦어져 70분 걸린 문제

 

처음에는 그래프 표현을 위해 ArrayList를 사용했는데, add와 get밖에 사용하지 않고, 두 연산 모두 O(1)밖에 걸리지 않아 큰 문제가 없다고 판단했다.

그러나 한 테스트케이스에서 시간초과 판정을 받아 다시 고민해보니

 

모든 노드의 간선이 최대 1개라는 점을 이용하면 1차원 배열로도 그래프 표현이 가능하다는 사실을 깨달았고,

1차원 배열을 통해 구현하니 바로 통과가 되었다.