프로그래머스 (Dev-Matching 기출) | LV.3 다단계 칫솔 판매 - DFS 재귀 문풀 (Java)

⬛ 프로그래머스 (Dev-Matching 기출) | LV.3 다단계 칫솔 판매 -  DFS 재귀 문풀 (Java)

https://school.programmers.co.kr/learn/courses/30/lessons/77486

프로그래머스

 

문제 설명

---

💚문제 접근 방식

문제를 보면서 DFS로 각 i에 대한 부모로 거슬러 올라가며 금액만 누적처리해주면 되겠다고 생각헀다. 그런데, 이름이 많으니까 좀 헷갈려서 나의 경우에는 각 이름에 대한 인덱스로 접근하여 처리했다. 

enroll은 Map에 인덱스 담아서 Key로 idx바로 찾도록 해주고, referral은 각 i의 부모 이름 정보가 담겨있는데, 이는 parent[i]에 idx 담아서 처리했다. 결과적으로 각 i에 대한 부모 parent[]에 담아두고 매번 처리할 때마다 parent[]의 부모값을 재귀로 거슬러 올라가며 처리해준 방식이다.

그럼에도 DFS를 구현하는 과정에서 크게 두 가지 부분에서 애를 먹었는데 내용은 다음과 같다.

 

🎈 [주의] 위로 올릴 값에는 ceil로 계산하면 안 되는 이유 

처음에는 위로 올릴 분배값과 현재 i가 먹는 값 둘다 ceil로 올려 계산했는데 생각이 짧았음을 알았다.

 예를 들어, 199에 대해 0.1은 올리고 0.9는 현재 i가 먹는다고 치면 문제가 생기기 때문이다. 199에 대한 0.1 값은 19.9 이고, 이걸 ceil로 올리면 20이 되는데 왜 이렇게 머리가 단순할까.. 난 처음에 왜 그렇게 풀었을까...

정리하자면, 현재 i의 경우 문제에서 요구했던 (10% 를 계산할 때에는 원 단위에서 절사하며, 10%를 계산한 금액이 1 원 미만인 경우에는 이득을 분배하지 않고 자신이 모두 가집니다.) 이 부분 때문에 현재 i가 먹는 금액은 ceil 처리를 해도 된다.

그러나, 위로 올릴 0.1 값은 올림 처리를 해서는 안된다. 맨 처음 제출했던 코드는 아래와 같고, 계속해서 다음 깊이의 price에 대해 0.1을 곱하여 ceil로 지칭했는데 예제는 통과하고 최종 제출해서 실패했다.따라서 올릴 값에 대해서는 매번 10으로 나누는 게 더 정확하고 이왕이면 올릴 값을 따로 구해서 그걸 현재 price 에서 뺴주며 갱신하는 게 더 낫다.

    //처음에 제출했던 틀린 코드
    private static void DFS(int idx, int price){
        if(parent[idx] == 0){
            answer[idx] += (int) Math.ceil(price * 0.9);
            return;
        }else{
            answer[idx] += (int) Math.ceil(price * 0.9);
            DFS(parent[idx], (int) Math.ceil(price * 0.1));
        }
    }

 

🎈 [주의] parent[ ] = 0을 재귀 복귀 시점으로 사용하면 문제가 생겼던 이유

설명

두 번째 문제점은 parent[idx]=0 이 되는 부분이 center를 제외한 가장 윗 부분의 부모라고 생각했기 때문에 parent[]=0 되는 지점을 DFS 종료 지점으로 썼던 게 문제였다.

 처음엔 (-)에 대해서 continue를 줬기 때문에 초기값인 0을 갖게 만들었는데, 이럴 경우 부모 세팅을 다 한 상태에서 0을 갖는 애가 (-) 인 애만 있는 게 아니라, 진짜 0번을 부모로 갖는 애도 있어서 DFS 복귀 시점을 0으로 두면 부정확한 처리를 한다. 따라서 (-) 를 갖는 애는 -1로 두는 게 정확한 처리다.

처음에는 center는 어차피 enroll에 포함이 안되어 있고, 최종 반환해줄 answer에도 포함 안된 값이라서 상관없을 줄 알았는데 사실 parent[i]의 정확한 정의가 i에 대한 부모 idx 저장용이었다면 (-) 를 갖는 애의 인덱스는 -1을 줬어야 하는 게 맞다. 처음부터 고려해야 헀다 ㅠ

---

1) HashMap으로 각 String에 대한 Index를 줬다. map에 getKey()으로 사람이름 idx 곧장 찾기 위함

 

2) parent[i] 에 referral의 이름에 대한 idx값을 각 i에 대한 부모로 지정해줬다. 그리고 이때, 만약 map에 없는 이름이라면 (즉, - 인 애들) 얘네는 부모가 center인 애들이라 -1을 지칭해줬다.

→ 처음에는 기본값 0으로도 된다 생각했는데, 추천인 없어도 0번을 부모로 인식하던 문제 때문에 굳이 -1로 지정해줘야 했다.

 

3) seller의 정보를 순회하면서 현재의 price값과 그걸 벌어온 현재 사람의 idx를 DFS에 주고 answer를 계속 갱신했다.

 

4) DFS는 내부적으로 현재 answer[idx] 에 대한 price 의 0.9 값을 누적하고 부모가 -1이 나오기 전까지 거슬러 올라가면서 10프로를 계속 올려보낸다. 그 깊이가 -1이 나올 때까지 쭉 거슬러 올라가며 갱신하면 answer에는 결국 각 idx가 누적하여 먹은 값이 계산된다.

import java.util.*;
class Solution {
    private int[] answer;
    private int[] parent;
    //재귀
    private void DFS(int idx, int price){
        int referral = price / 10;
        answer[idx] += price - referral;

        if (parent[idx] != -1 && referral > 0) {
            DFS(parent[idx], referral);
        }
    }
    //솔루션 함수
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int N = enroll.length;
        answer = new int[N];

        Map<String, Integer> map = new HashMap<>();
        for(int i=0; i<N; i++){
            map.put(enroll[i], i);
        }

        //부모 세팅
        parent = new int[N];
        for(int i=0; i<N; i++){
            if(map.containsKey(referral[i])){
                parent[i] = map.get(referral[i]);
            } else {
                parent[i] = -1;
            }
        }

        for(int i=0; i<seller.length; i++){
            int cur_price = amount[i] * 100;
            int cur_idx = map.get(seller[i]);

            DFS(cur_idx, cur_price);
        }

        return answer;
    }
}

💚시간복잡도

enroll 배열 referral 배열에 대해서 Map 세팅 parent 세팅할 떄 for 문 1번씩 돌기 때문에 최악으로 O(10^4 + 10^4), seller 길이만큼 돌면서 재귀함수 호출하고 있는데, seller 길이가 최대 10^5 이기 때문에 최악으로 20만+10만 정도여서 시간 내에 동작한다고 본다.