[프로그래머스] 다단계 칫솔 판매

문제

다단계 칫솔 판매

판매원 young 에 의하여 1,200 원의 이익이 발생했습니다. young 은 이 중 10% 에 해당하는 120 원을, 자신을 조직에 참여시킨 추천인인 edward 에게 배분하고 자신은 나머지인 1,080 원을 가집니다. edward 는 young 에게서 받은 120 원 중 10% 인 12 원을 mary 에게 배분하고 자신은 나머지인 108 원을 가집니다. 12 원을 edward 로부터 받은 mary 는 10% 인 1 원을 센터에 (즉, 민호에게) 배분하고 자신은 나머지인 11 원을 가집니다. 이 상태를 그림으로 나타내면 아래와 같습니다.

풀이

• 특정 리프노드에서 루트노드까지 모든 경로에 있는 노드의 profit을 업데이트 시켜야함
• 부모노드의 값을 계속 업데이트 시켜야하기 때문에 재귀, 해쉬맵, 트리 등으로 풀 수 있음
• 그림이 트리로 되어 있기도 하고 트리 연습도 할겸 트리로 풀었음

코드

function solution(enroll, referral, seller, amount) {
  const tree = new Tree();
  const answer = []
  tree.insert(enroll, referral, seller, amount);
  
  for(let i = 0; i < seller.length; i++){
    const s = seller[i]
    const p = amount[i] * 100
    tree.traverseUp(s, p, 0)
  }
  
 
  for(let i = 0; i < enroll.length; i++){
    const e = enroll[i]
    answer.push(tree.getProfit(e))
  }
  
  return answer;
}

class Node {
  constructor(name, parent, profit) {
    this.name = name;
    this.parent = parent ?? null;
    this.profit = profit ?? 0;
    this.children = [];
  }
}

class Tree {
  constructor() {
    this.root = new Node('-', null, 0);
    this.nodeMap = new Map()
  }

  insert(enroll, referral, seller, amount) {
    this.nodeMap.set("-", this.root)
    
    for (let i = 0; i < enroll.length; i++) {
      const name = enroll[i];
      const node = new Node(name, referral[i], 0);
      this.nodeMap.set(name, node)
    }

    for (let i = 0; i < referral.length; i++) {
      const parentName = referral[i];
      const childNode = this.nodeMap.get(enroll[i])
      const parentNode = this.nodeMap.get(parentName)

      if (parentNode && childNode) {
        parentNode.children.push(childNode);
        childNode.parent = parentNode;
      }
    }
  }

  findNode(nodeName) {
    if (!this.nodeMap.get(nodeName)) return;
    return this.nodeMap.get(nodeName)
  }

  traverseUp(nodeName, profit, sum) {
    const node = this.findNode(nodeName);
    if (!node) return sum
    if (node.parent || nodeName === "-") {
      const left =  Math.floor(profit * 0.1)
      let newProfit = profit - left
      node.profit += newProfit
      if(left) this.traverseUp(node.parent?.name, left, newProfit);
    } else {
      return sum
      console.log('더 이상 부모 노드가 없습니다.');
    }
  }
  
  getProfit(nodeName){
    const node = this.findNode(nodeName);
    if (!node) return 0
    return node.profit
  }
}

정리

• 문제 3개만 시간 초과나서 별 짓을 다 해봤는데 안 돼서 좌절하다가 [질문하기]에 profit 계산이 필요 없는 노드도 탐색하면 시간 초과난다는 글을 보고 traverseUp에 조건 하나 추가했더니 통과했다. 이래서 코딩이 어려운데 재밌다