[C#] 다단계 칫솔 판매

프로그래머스 문제

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

풀이 후기

1. 분석

그냥 구현인가? 자식을 저장하는 그래프가 아니라 부모를 저장하는 그래프를 만들어서 풀었다. 보니까 DFS로도 푸는 것 같음.

그냥 뻔한 소리지만 주의해야 할 점은

(int)(m * 0.1) + (int)(m * 0.9) != m

int로 변환할 때 소수점을 버리기 때문에 두 수를 더해도 m이 안나온다. 그리고 배열은 이름으로 제공되기 때문에 find 도배를 하면 시간이 터진다. 딕셔너리나 맵을 쓰도록 하자. 이 외에는 그냥 구현만 해서 딱히 쓸 말이 없다.

2. 실행결과

3. 코드

using System;
using System.Linq;
using System.Collections.Generic;

public class Solution {
    
    public class Node{
        public int money = 0;
        public List<Node> parents = new List<Node>();

        public void AddParent(Node n){
            parents.Add(n);
        }
        
        public void GiveToParents(int m){
            var left = (int)(m * 0.1);
            
            if(1 <= left){
                money += m - left;
                foreach(var p in parents){
                    p.GiveToParents(left);
                }
            }
            else{
                money += m;
            }
        }
    }
    
    public int[] solution(string[] enroll, string[] referral, string[] seller, int[] amount) {
        var nodes = enroll.ToDictionary(n => n, _ => new Node());
        
        for(int i = 0; i < referral.Length; i++){
            if(referral[i] != "-"){
                var find = nodes[referral[i]];
                nodes[enroll[i]].AddParent(find);
            }
        }
        
        for(int i = 0; i < seller.Length; i++){
            var find = nodes[seller[i]];
            find.GiveToParents(amount[i] * 100);
        }
        
        return nodes.Select(n => n.Value.money).ToArray();
    }
}