프로그래머스(2021 Dev-Matching) - 다단계 칫솔 판매

문제 출처:https://programmers.co.kr/learn/courses/30/lessons/77486

코딩테스트 연습 - 다단계 칫솔 판매

 

지문처럼 단방향 그래프로 설정하여 풀면 간단히 해결할 수 있는 문제다.

초기 설정은 enroll의 부모는 referral로 하여 ArrayList배열을 설정해주면 된다. 보기에는 문자열로 되어있으므로 필자는 enroll에 이름들을 순서대로 hashmap으로 해서 0부터 순차적으로 값을 주었다.

즉, John은 1, mary는 2... 이런식으로 말이다.

 

//hashmap으로 각각 enroll의 사용자에게 0부터 인덱스값 부여
        HashMap<String,Integer> hm = new HashMap<>();
        for(int i=0;i<enroll.length;i++){
            hm.put(enroll[i],i);           
        }

 

 

다음으로  HashMap의 key를 참고하여 리스트 배열에 연결시켜주었다.

for(int i=0;i<enroll.length;i++){
            String key = enroll[i];
            String refer = referral[i];
            if(refer.equals("-"))
                continue;
            int from = hm.get(key);
            int to = hm.get(refer);
            list[from].add(to);
        }

 

 

이제 마무리로 seller에서 하나씩 읽어들이면서 각자의 부모 노드를 찾아가면서 값을 경신해 나가면 된다.