[JS] 다단계 칫솔 판매

문제

프로그래머스

 

 

풀이

문제를 보고 인물들의 계층 구조를 보고 먼저 생각한 알고리즘은 DFS이다.

 

이 문제의 경우 재귀를 이용하는 방법 대신 Stack으로 탐색 노드를 저장해 pop하여 탐색할 수 있도록 설계했다.

 

이 문제에서 햇갈렸던 점이 소개해 준 사람이 얻는 이득을 계산하는 로직이였는데, 이는 이득의 합 계산이 아닌 각 이득의 10퍼씩 전달해야한다. 이말은 (10 + 20 + 30) * 0.1이 아니라 (10 * 0.1)+(20 * 0.1)+(30 * 0.1)으로 계산해야 한다.

 

코드

function solution(enroll, referral, seller, amount) {
  const answer = [];
  const pos = { "-": [] };
  const stack = [['-', null]];
  const visited = { '-': false };
  const m = seller.reduce((acc, cur, idx) => {
    acc[cur] ? acc[cur].push(amount[idx] * 100) : acc[cur] = [amount[idx] * 100];
    return acc;
  }, {})
    
  enroll.forEach(e => visited[e] = false);
    
  referral.forEach((e, i) => {
    const name = enroll[i];
    pos[name] = [];
    pos[e].push(name);
  });
    
  while (stack.length) {
    const [cur, parent] = stack.pop();
    if (visited[cur]) {
      if (m[cur] && cur !== '-') {
        for (let i = 0; i < m[cur].length; i++) {
          const income = Math.floor(m[cur][i] / 10);
          if (income === 0) continue;
          m[cur][i] -= income;
          m[parent] ? m[parent].push(income) : m[parent] = [income];
        }
      }
      continue;
    }
    visited[cur] = true;
    stack.push([cur, parent]);
        
    for (let name of pos[cur]) {
      if (!visited[name]) stack.push([name, cur]);
    }
  }
  return enroll.map(name => m[name] ? m[name].reduce((a, b) => a + b) : 0);
}