프로그래머스 - Lv.3 다단계 칫솔 판매 (트리 | DFS) JS

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

문제 지문이 굉장히 긴 편이기에, 문제의 일부만 대체 후 설명한다.

문제는, 각 판매원의 이름을 담은 배열 enroll, 각 판매원을 다단계 조직에 참여시킨 다른 판매원의 이름을 담은 배열 referral, 판매량 집계 데이터의 판매원 이름을 나열한 배열 seller, 판매량 집계 데이터의 판매 수량을 나열한 배열 amount가 매개변수로 주어진다.

여기서 중요한 규칙이 있는데, 만약 판매자가 a금액 만큼 판매한 경우, 해당 금액의 10%를 자신을 다단계에 참여시킨 판매원에게 지급하며 남은 90%의 금액을 자신이 갖게 된다. (이때, 10%의 금액을 받은 판매원 역시 해당 금액의 10%를 자신을 참여시킨 판매원에게 지급하며, 만약 주어야 하는 금액이 1원 미만이라면 주지 않는다.)

따라서, 주어진 데이터를 통해 각 판매원이 득한 이익금을 나열한 배열을 리턴하도록 로직을 완성하면 된다.

 

문제 해결 방식

먼저 각 enroll, referral, seller의 배열 안에 있는 원소가 알파벳으로 이루어진 이름이기 때문에 해당 이름들을 매핑했다.

이후, 다단계 구조가 트리 구조와 일치하며, 판매자 -> 판매자의 추천인 -> 추천인의 추천인 순으로 수익이 분배되기 때문에 풀이 방식에 DFS 알고리즘을 접목시켰다.

 

전체 소스 코드

function solution(enroll, referral, seller, amount) {
  const namesTable = {};
  const N = enroll.length + 1;
  enroll.forEach((el, idx) => (namesTable[el] = idx + 1));

  const roots = {};
  for (let i = 0; i < N; i++) {
    roots[i] = i;
  }

  referral.forEach((el, idx) => {
    // 여기서 0 은 최상위 루트인 'center'
    el === "-" ? (roots[idx + 1] = 0) : (roots[idx + 1] = namesTable[el]);
  });

  const total = Array.from({ length: N }, () => 0);
  function DFS(node, money) {
    const nextMoney = parseInt(money * 0.1);
    total[node] += parseInt(money - nextMoney);

    // 도착한 node가 0, 즉 센터로 최상위 루트거나, 전달할 금액이 0원이면 재귀 종료
    if (!node || !nextMoney) return;

    const nextNode = roots[node];
    DFS(nextNode, parseInt(nextMoney));
  }

  seller.forEach((node, idx) => {
    const money = amount[idx];
    DFS(namesTable[node], money * 100);
  });

  return total.slice(1);
}