C# 다단계 칫솔 판매 - DFS / 프로그래머스 [Lv.3]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/77486

 

문제가 너무 길어서 일부만 캡처

 

1차 시도

public int[] solution(string[] enroll, string[] referral, string[] seller, int[] amount) 
{
    int[] answer = new int[enroll.Length];

    var enrollDict = Enumerable.Range(0, enroll.Length)
                               .ToDictionary(e => enroll[e], e => referral[e]);

    for(int i = 0; i < seller.Length; ++i)
    {
        string s = seller[i];
        int money = amount[i] * 100;

        string refer = string.Empty;
        while(true)
        {
            int tenPercent = (int)Math.Floor(money * 0.1);
            AddMoney(answer, enroll, s, money - tenPercent); // 자기자신에게 90% 배분

            refer = enrollDict[s];
            if(refer == "-")
                break;

            s = refer;
            money = tenPercent;
        }
    }

    return answer;
}

void AddMoney(int[] answer, string[] enroll, string owner, int money)
{
    int index = Array.IndexOf(enroll, owner);
    answer[index] += money;
}

자신에게 90%이득을 남기고, 금액을 다음사람에게 넘기는 방식으로 루프문으로 하면 간단하게 구현이 가능하다. 

그런데 재귀로 구현한 것도 아닌데 시간초과 발생.

enroll 길이 10,000 이하 / seller 길이 100,000 이하

최적화가 필요하다.

 

나의 풀이

public int[] solution(string[] enroll, string[] referral, string[] seller, int[] amount) 
{
    var enrollDict = Enumerable.Range(0, enroll.Length)
                               .ToDictionary(e => enroll[e], e => referral[e]);

    var moneyDict = Enumerable.Range(0, enroll.Length)
                               .ToDictionary(e => enroll[e], e => 0);

    for(int i = 0; i < seller.Length; ++i)
    {
        string s = seller[i];
        int money = amount[i] * 100;

        while(true)
        {
            int tenPercent = (int)Math.Floor(money * 0.1);
            moneyDict[s] += money - tenPercent; // 자기자신에게 90% 배분

            if(tenPercent == 0) break;
            if(enrollDict[s] == "-") break;

            s = enrollDict[s];
            money = tenPercent;
        }
    }

    return enroll.Select(e => moneyDict[e]).ToArray();
}

1. 

금액을 지급할 때 IndexOf로 위치를 찾는 부분을 Dictionary로 변경하여 최적화하였다. 

2.

분배금이 0일때 break를 해주는 부분이 누락되서 추가하였다.