프로그래머스: 다단계 칫솔 판매 - javascript(구현 및 dfs)

깔끔한 문제였던 것 같다... 

내가 풀었기 때문에 ^^ 좋은 문제인 것 처럼 느껴짐 ㅎㅎ 

 

문제 출처 

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

프로그래머스

문제 풀이 힌트 

 

1) 객체를 2개 생성 

- 각 사람을 index로 활용하기 위한 map 객체 

- 각 사람을 key로, 추천인을 value로 한 map 객체  

 

2) 현재 사람의 이익을 계산하는 함수 

- 현재 사람은 90% 를 가지고, 다음 추천인에게는 절사한 10%를 준다. 

=> 즉, 추천인의 10%를 구한 뒤 절사한(소수점 빼기) profit을 먼저 구한뒤, 나머지를 현재 사람한테 줘야 한다. 

 

3) 문제를 보면 node의 꼬리물기 형식으로 되어있다. => `dfs`를 활용하도록 하자.

 

정답 풀이 코드 

function solution(enroll, referral, seller, amount) {
   let answer = new Array(enroll.length).fill(0); //각 사람에 대한 이익 더해가는 배열 
   let nameToIndex = new Map(); //사람을 index로 표현하기 위해 Map 객체 생성
   enroll.forEach((name, index) => nameToIndex.set(name, index)); //key로 사람이름을, 값으로 index를, 
   
   let map = new Map(); //각 사람에 따른 추천인 정리하기 위해 Map 객체 생성   
   for(let i=0; i<enroll.length; i++){
       map.set(enroll[i], referral[i]); //사람을 key로, 추천인을 value로!
   }
   
   //seller반복문, 한번의 판매 때 전체 총이익을 채워나갈 것임. (dfs이용: 꼬리물기식)
    for(let i=0; i<seller.length; i++){
       const sell = seller[i]; //판매를 일으킨 사람 이름 
       const profit = amount[i] * 100; //판매수 * 100원 
       dfs(sell, profit, map, answer, nameToIndex); //총이익 분배 시작해보자. 
    }
    return answer; //seller 반복문이 끝났을 때 answer 배열엔 각 사람에 대한 총이익이 담겨있음. 
}

//현재 node(dfs에 node 변수 등장함)에 대한 이익을 계산하는 함수 
function cal(profit){
   let reff = Math.floor(profit * 0.1); //나를 추천해준 사람의 이익은 원 단위에서 절사한다고 문제에서 제시. 
        return profit - reff; //총 이익 - 추천인한테 줄 돈
}


//dfs 함수를 통해서 현재 사람은 90% 가져가고 추천인한테 절사한 10%를 주는 꼬리물기 계산을 하는 것. 
//변수 설명: "node"는 현재 "profit"의 90%를 갖는 사람이다. 
//변수 설명: "answer"는 각 사람에 대한 실시간 이익 정보가 담겨있다.
//변수 설명: "map","nameToIndex"는 추천인이 누군지, 이름에 따른 index를 알기 위해 가져온 것. 

function dfs(node, profit, map, answer, nameToIndex){
    if(profit < 1) return; //profit이 1미만이라면 현재 node가 가져갈 이익이 없음. 
    if(node === '-') return; //node가 '-'라면, 그건 계산하지 않아도 됨 (문제에선 center) 
    
    let idx = nameToIndex.get(node); //nameToIndex를 활용해서 node의 idx 값 가져온다 
    const refNode = map.get(node); //map을 활용하여 node의 추천인을 가져온다. 
    
    let nodeProfit = cal(profit); //현재 node가 가져갈 이익 계산 
    let referralProfit = profit - nodeProfit; //추천인한테 줄 이익 계산(전체-node가져갈 이익) 
    
    answer[idx] += nodeProfit; //현재 node의 실시간 총이익에 위에서 구한 이익(nodeProfit) 더한다. 
    dfs(refNode, referralProfit, map, answer, nameToIndex); //다음 노드 refNode를 방문하자. 추천인 이익(referralProfit)과 함께
}

 

Only 풀이 코드 

function solution(enroll, referral, seller, amount) {
   let answer = new Array(enroll.length).fill(0); 
   let nameToIndex = new Map(); 
   enroll.forEach((name, index) => nameToIndex.set(name, index)); 
   let map = new Map(); 
    
   for(let i=0; i<enroll.length; i++){
       map.set(enroll[i], referral[i]); 
   }
    for(let i=0; i<seller.length; i++){
       const sell = seller[i]; 
       const profit = amount[i] * 100;
       dfs(sell, profit, map, answer, nameToIndex); 
    }
    return answer; 
}

function cal(profit){
   let reff = Math.floor(profit * 0.1); 
        return profit - reff; 
}

function dfs(node, profit, map, answer, nameToIndex){
    if(profit < 1) return; 
    if(node === '-') return; 
    
    let idx = nameToIndex.get(node); 
    const refNode = map.get(node);
    
    let nodeProfit = cal(profit); 
    let referralProfit = profit - nodeProfit; 
    
    answer[idx] += nodeProfit; 
    dfs(refNode, referralProfit, map, answer, nameToIndex);
}

 

알고가는 ppoint