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

문제 출처

프로그래머스 lev3 - 다단계 칫솔 판매

나의 풀이

1차시도(76.9/100)

시간초과/런타임에러

function solution(enroll, referral, seller, amount) {
  let sum = new Array(enroll.length).fill(0)

  function dfs(temp, seller){
    let idx = enroll.indexOf(seller)
    let next = referral[idx]

    if(next === '-') return
    else {
      temp.push(next)
      dfs(temp, next)
    }
  }

  function calc(total){
    let next = (total * 10/100) > 0 ? parseInt(total * 10/100) : 0
    let curr = total - next 
    return [curr, next]
  }

  seller.map((v,i) => {
    let index = enroll.indexOf(v)
    let total = amount[i]*100 
    let [curr, next] = calc(total)
    let link = [v]

    dfs(link, v)

    sum[index] += curr 
    curr = next 
    for(let k=1; k<link.length; k++){
      let [c, n] = calc(curr)

      sum[enroll.indexOf(link[k])] += c 
      curr = n
    }
  })
  return sum 
}

console.log(
  solution(
    ["john", "mary", "edward", "sam", "emily", "jaimie", "tod", "young"], // enroll
    ["-", "-", "mary", "edward", "mary", "mary", "jaimie", "edward"], // referral 
    ["young", "john", "tod", "emily", "mary"], // seller
    [12, 4, 2, 5, 10]
  )
) // [360, 958, 108, 0, 450, 18, 180, 1080]

아무래도 dfs가 너무 깊어서 생기는 문제인 것 같기도..

일단 불필요한 코드를 최대한 줄였다. 그리고 런타임 에러도 해결했다.
total(분배금)이 0인데도 dfs를 호출하면 런타임 에러가 발생한다.
그래서 종료조건으로 total === 0를 추가하니 런타임 에러는 사라졌다.

하지만 여전히 시간초과가 발생한다...

function solution(enroll, referral, seller, amount) {
  let sum = new Array(enroll.length).fill(0)
  
  function calc(total){
    let pure = total * 10/100
    let next = pure > 0 ? parseInt(pure) : 0
    let curr = total - next 
    return [curr, next]
  }

  function dfs(currVtx, total){
    if(currVtx === '-' || total === 0) return
    else {
      let index = enroll.indexOf(currVtx)
      let parent = referral[index]

      let [currValue, nextValue] = calc(total)

      sum[index] += currValue 
      total = nextValue
      dfs(parent, total)
    }
  }

  seller.map((v,i) => {
    let total = amount[i]*100 
    dfs(v, total)
  })

  return sum 
}

다른 풀이 (dfs)

같은 dfs인데 성능 차이가 크게 발생한다.
왜 그럴까?

1. 일단 indexOf 메서드를 사용하지 않았다.
2. 내가 문제를 잘못 이해한 지점이 있는데,
   내가 dfs를 사용한 방식은 각 노드마다 index가 전부 달라질 때를 가정한 방식이다.
   반면, 이 문제에서는 index가 enroll 배열과 referral 배열밖에 없다. 두 배열의 index만 미리 구해놓으면 계속해서 indexOf 메서드를 사용할 필요가 없다.
   그리고 index를 미리 구해놓을 때 map을 사용해서 key 이름으로, value를 index로 미리 저장해놓으니 index를 빠르게 찾을 수 있게 된다.

function solution(enroll, referral, seller, amount) {
  const len = enroll.length 
  const hash = new Map()
  const edge = Array(len)
  const answer = Array(len).fill(0)

  function dfs(num, money){
    const next = edge[num]
    const nextMoney = Math.floor(money * 0.1)
    const currMoney = money - nextMoney 

    answer[num] += currMoney 

    if(next !== null && nextMoney !== 0) dfs(next, nextMoney)
  }

  for(let i=0; i<len; i++) hash.set(enroll[i], i)

  for(let i=0; i<len; i++){
    const ref = referral[i]

    if(ref === '-'){
      edge[i] = null 
      continue
    }
    edge[i] = hash.get(ref)
  }

  for(let i=0; i<seller.length; i++){
    const num = hash.get(seller[i])
    const money = amount[i]*100 

    dfs(num, money)
  }
  return answer  
}

다른 풀이 2

function solution(enroll, referral, seller, amount) {
  const sells = seller.reduce((sells, sell, i) => ((sells[sell] = sells[sell] || []).push(amount[i] * 100), sells), {})
  const members = enroll.reduce((members, member, i) => (members[member] = {
      parent: members[referral[i]] || null,
      sells: sells[member] || [],
      profit: 0,
  }, members), {})

  for (let member of Object.values(members)) {
      for (let sell of member.sells) {
          let profit = sell
          let currentMember = member

          while (currentMember && profit) {
              let parentProfit = Math.floor(profit / 10)
              let myProfit = profit - parentProfit

              currentMember.profit += myProfit

              currentMember = currentMember.parent
              profit = parentProfit
          }
      }
  }

  return enroll.map(member => members[member].profit)
}

참고

프로그래머스 : 다단계 칫솔 판매 (JavaScript)