2021 Dev-Matching 웹 백엔드 개발자 선발 문제 중 레벨 3의 문제이다.

문제

문제 링크
문제 설명이 복잡한 관계로 링크로 대신한다.
문제의 핵심은 다음과 같다.
1. 다단계조직 구조와 수익을 낸사람, 금액이 주어진다.
2. 모든 수익은 본인이 90% 상위사업자에게 10%가 돌아가며 1원이하 단위는 절삭한다.
3. 하위사업자로부터 수수료로 받은 10%의 금액 또한 다시 90:10으로 나누어 10%를 상위사업자에게 배분한다.
4. 모든 과정을 마쳤을 때 다단계 조직원별 수익이 얼마나 났는지 출력한다.

풀이과정

<입력>

1. 다단계 직원 목록 "enroll"(Array)
2. 직원별 상위사업자 "referral(Array)
3. 칫솔 판매한 직원 "seller"(Array)
4. 칫솔 판매 개수 "amount"(Array)

1,2번과 3,4번은 각각 index로 연관되어있다. 즉 enroll에서 i번째 있는 사람의 상위사업자는 referral의 i번째 사업자이며, 3번의 i번째 판매자가 판매한 칫솔갯수는 amount의 i번째 숫자이다.

<핵심 아이디어>

우선 이번 문제에서 가장 직관적으로 문제를 해결하려면 칫솔을 판매한 직원으로부터 상위사업자 방향으로 탐색을 진행해야한다. 즉 한 node를 선택했을때 그것의 parentNode가 무엇인지 알아야한다. 그리고 그 parentNode를 따라 올라가는 재귀함수를 구현한다.

let graph={}                             //그래프의 key는 사업자, value는 상위사업자로 표현할것
    let result = {}
    for(let i=0;i<enroll.length;i++){
        graph[enroll[i]]=referral[i]     //enroll의 i번째 사업자의 상위사업자는 referral의 i번째 사업자
        result[enroll[i]]=0              //일단 결과를 넣어줄 객체를 하나 더 만든다.
    }

function distribute(name,money){          //사업자 이름과 금액을 받아서
        if(money===0) return              //금액이 0이면 바로 종료
        let divide = Math.ceil(money*0.9) //사업자가 가질 금액
        result[name] += divide            //결과에 금액(90%)을 더해주고
        distribute(graph[name],Math.floor(money*0.1)) //상위사업자에게 나머지 10% 금액으로 넘겨준다. 
    }

이제 distribute 함수에 최초 판매자와 판매금액을 넣어주면 최상위사업자까지 재귀함수를 돌면서 10%씩 수익을 분배할것이다

<판매금액 투입하기>

distribute 함수에 넣어줄 name과 money 를 한쌍으로 배열에 넣어보자. 칫솔 하나는 100원이므로 판매량에 100을 곱하면 되겠다.

let earn = seller.map((v,i)=>[v,amount[i]*100]) // v=판매자 이름,amount[i]*100= 판매금액

그다음은 이름과 판매액을 함수에 순서대로 넣어주면된다.

for(const [name,money] of earn){
        distribute(name, money)
    }

위 과정을 끝내고 나면 result에 {이름: 총수익}의 결과값들이 들어가있을텐데 enroll에 나온 순서대로 배열에 넣어주면 된다.

let answer=[]
    for(const name of enroll){
        answer.push(result[name])
    }
    return answer

결과는?

<피드백>

이 문제를 풀면서 몇가지 착각할만한 부분이 있었는데, 1원 이하 단위를 절삭하기 때문에 판매자가 같다고해서 판매금액을 합해서 넘겨주면 안된다는 것이다.
처음에 미리 판매금액 총액을 합해두면 효율적일것 같아서 합하여 넘겨준 적이 있었는데 거의 모든 테스트에서 실패가 나왔다.
예를들면 판매금액이 9원과 8원인 경우, 각각 계산했을때는 10%의 1원 미만은 절삭하여 넘겨주기 때문에 9원의 10%인 0.9, 8원의 10%인 0.8 둘다 0원이 되어 상위사업자에게 돈을 주지 않아도 되지만 이를 먼저 합해버리면 17원이 되어 17원의 10%인 1.7원=>1원을 상위사업자에게 주어야되는 것이다.
가끔 문제를 접하다보면 수학적 직관력도 중요한 문제들이 보이는것같다.

<전체코드>

function solution(enroll, referral, seller, amount) {
    let graph={}
    let result = {}
    for(let i=0;i<enroll.length;i++){
        graph[enroll[i]]=referral[i]
        result[enroll[i]]=0
    }
    function distribute(name,money){
        if(money===0||result[name]==undefined) return
        let divide = Math.ceil(money*0.9)
        result[name] += divide
        distribute(graph[name],Math.floor(money*0.1))
    }
    let earn = seller.map((v,i)=>[v,amount[i]*100])

    for(const [name,money] of earn){
        distribute(name, money)
    }
    let answer=[]
    for(const name of enroll){
        answer.push(result[name])
    }
    return answer
}