다단계 칫솔 판매 (프로그래머스 : C#)

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

📕 문제 설명

다단계 조직에서 칫솔을 판매한다. 이때, 본인을 추천해준 추천인에게 판매 금액의 10%씩 분배한다. 판매한 칫솔 개수가 주어졌을 때, 각 멤버별 이익금의 총합을 계산해 enroll 순서대로 나열하여 반환하기

추가 설명

다음 사진을 보면 더 잘 이해가 된다. 만약 young이 1200원을 벌게 되면 그 금액의 10%를 edward에게 분배한다. 그럼 edward는 120원을 받게 되고 여기서 10%를 다시 추천인인 mary에게 분배해준다. 마지막으로 mary의 12원에서 10%를 center인 민호에게 나눠준다.

이러한 방식으로 모든 seller들을 돌면서 최종적으로 얼만큼의 수익을 얻는 지를 반환하는 문제이다.

• Input

조직 구성원 (민호 제외), referral (i 번째에 있는 이름은 배열 enroll 내에서 i 번째에 있는 판매원을 조직에 참여시킨 사람의 이름 , 어느 누구의 추천도 없이 조직에 참여한 사람 = ‘-’), 판매자, 판매 개수

• Output

판매량 보고 이익금 총합 계산해 enroll 순서대로 나열

풀이

leaf에서 root쪽으로만 방향이 있는 단방향 그래프를 생성한 후, seller를 돌면서 판매한 사람의 이익에서 10%를 윗 방향으로 주는 방식으로 코드를 작성했다.

using System;
using System.Collections.Generic;
public class Solution {
    int[] answer;
    List<int>[] graph;
    public void DFS(int start, int amount)
    {
        if(amount == 0) return; // 수익 0원이면 그만 
        for(int i = 0; i < graph[start].Count; i++)
        {
            DFS(graph[start][i], (int) (amount * 0.1)); // 내 위에 추천인 있으면 재귀
        }
        answer[start] += (int)Math.Ceiling(amount*0.9); // 추천인에게 10% 준 후 남은 돈 합함
    }
    public int[] solution(string[] enroll, string[] referral, string[] seller, int[] amount) {
        answer = new int[enroll.Length];
        graph = new List<int>[enroll.Length];
				// 인덱스 뽑기 위한 딕셔너리
        Dictionary<string, int> indexDict = new Dictionary<string,int>();
				// 그래프 초기화
        for(int i = 0; i < enroll.Length; i++) 
        {
            indexDict[enroll[i]] = i;
            graph[i] = new List<int>();
        }
        for(int i = 0; i < referral.Length; i++)
        {
            if(referral[i] != "-") // 민호랑 바로 연결되지 않은 경우
            {
                int index = indexDict[referral[i]];
                graph[i].Add(index); // 그래프 연결 (단방향) 아래 -> 위 
            }
        }
				// 칫솔 판매 이익 공유 시작 (재귀)
        for(int i = 0; i < seller.Length; i++)
        {
            int sellerI = indexDict[seller[i]];
            DFS(sellerI, amount[i]*100);
        }
        return answer;
    }
}

+) 계속 마지막 테스트 케이스 3개에서 에러가 발생했었다. 이는 amount가 0일때 재귀를 타고가는 것 때문이었어서 amount 0일 때 재귀를 멈추도록 작성하였다.

정확도 테스트