[JS] 다단계 칫솔 판매

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

프로그래머스

 

문제를 해결할 때 꼭 생각해야 하는 점이있다. (내가 실수한 부분이기도 하다)

 

처음에는 판매자의 모든 칫솔 판매량을 한번에 계산한 후 그 판매량의 10%를 부모에게 올라가도록 설계했었다.

 

하지만 위 방식으로는 해결할 수 없다. 

 

1개씩 10번 판매했을 경우와 10개씩 1번 판매했을 경우를 생각해 보자.

 

 

1개씩 10번 -> 100원의 이익이 10번 발생한 것이므로 2번 부모를 거치면 보낼 돈이 0원이 된다.

10개씩 1번 -> 1000원의 이익이 1번 발생한 것이므로 3번 부모를 거치면 보낼 돈이 0원이 된다.

 

 

이점을 생각하고 그래프에 부모,자식 정보를 저장하고 수익이 발생할때마다 부모에게 송금을 시켜주면 된다.

 

 

function solution(enroll, referral, seller, amount) {
    const graph = new Map()
    graph.set('-',{child :[],sell : 0,parent:null})
    
    for (let i = 0 ; i < enroll.length ; i++){
        const enrollName = enroll[i]
        const referralName = referral[i]
        
        graph.set(enrollName,{child :[],sell : 0,parent :referralName})
        graph.get(referralName).child.push(enrollName)
    }
    
    const calculateMoney = (name,money) => {
        const info = graph.get(name)
        
        const sendMoney = ~~(money / 10)
        info.sell += money - sendMoney
        
        if(info.parent && sendMoney!==0) calculateMoney(info.parent,sendMoney)
    }
    
    for (let i = 0 ; i < seller.length ; i++){
        const name = seller[i]
        const profit = amount[i]
        calculateMoney(name,profit * 100)
    }
    
    const ret = []
    for (const [name,info] of graph){
        if (name!=='-') ret.push(info.sell)
    }
    return ret
    
}