99클럽 코테 스터디 9일차 TIL [DFS]

 

- 오늘의 학습 키워드 : DFS 알고리즘

[문제 이름 : 다단계 칫솔 판매 (프로그래머스 77486, LV 3)]
문제 url : https://school.programmers.co.kr/learn/courses/30/lessons/77486

내가 작성한 코드는 아래와 같다.

package day_1105;

import java.util.HashMap;
import java.util.Map;

// 문제 link : https://school.programmers.co.kr/learn/courses/30/lessons/77486
public class pg_77486_l3 {
    static int[] answer;
    static Map<String, Integer> nameIndexMap = new HashMap<>();

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

        for (int i = 0; i < len; i++) {
            nameIndexMap.put(enroll[i], i);
        }

        for(int i=0; i<seller.length; i++) {
            String person = seller[i];
            DFS(person, amount[i] * 100, enroll, referral);
        }


        return answer;
    }

    static void DFS(String person, int amount, String[] enroll, String[] referral) {
        if (amount == 0) return;

        // 해당 사람의 인덱스 찾기
        int index = nameIndexMap.get(person);

        // 배분할 금액 계산
        int left = amount / 10;
        answer[index] += amount - left;

        // 추천인 있을 때만 DFS 수행
        if (!referral[index].equals("-")) {
            DFS(referral[index], left, enroll, referral);
        }
    }
}

 

풀이 과정 (풀이 시간 : 1시간)

트리로 접근해야 하는가 싶었지만, 자식 노드가 2개 이상인 경우도 있으므로 다른 접근 방법을 생각해 보았다.
매번 추천인을 찾기 위해 인덱스를 찾아야 하는데, 이때 시간복잡도를 고려하여 Map 자료구조를 사용하게 되었다.

1. 사람의 이름을 key로 하고, 해당 인덱스를 value로 하는 맵을 선언하고, 이를 저장한다.

2. Seller에 따라, DFS를 적용한다. amount가 0이 되는 경우 (10% 일 때 값 절삭이므로) return 해준다.
3. 추천인의 인덱스를 찾은 다음, 배분 금액을 계산한다. 계산 과정에서 90%는 본인에 해당하는 값으로 저장해준다.

4. 루트 노드('-')가 아닐 때까지, 반복해서 DFS를 실행한다.

내일은 목요일에 있을 면접에 대비해 질문을 추리고, 답변을 작성해볼 예정이다.