다단계 칫솔 판매

문제 접근

전형적인 DFS 문제이다. 조금 다른 점이라면, 낮은 level부터 높은 level로 가는게 아니라 그 반대의 방법으로 가는 것이다. 트리의 진행방향이 referral 라는 이름으로 정해져 있고 하나의 방향 밖에 없어서 간단하다.

따로 방문했는지 안 했는지 체크할 필요도 없고, 추천인 이름과 번 돈만 parameter로 넘겨주면 된다.

주의 할 점은 시간복잡도를 O(n)로 만드는 방법을 찾아야 하는 점이다.
seller 배열은 O(n)로 탐색할 수 밖에 없다.

  seller.forEach((name, idx) => {
    const money = amount[idx] * 100
    dfs(name, money)
  })

따라서 name 값의 enroll 배열 인덱스를 구하고 그 인덱스로 referal 배열 값에 접근해야한다. 만약 includes 나 indexOf 같은 메서드를 쓰면 어림도 없다. 😇
다음과 같이 hash를 만들자

 const enrollObj = Object.fromEntries(enroll.map((name, idx) => [name, { recommend: referral[idx], money: 0 }]))
  enrollObj['-'] = { recommend: 'no', money: 0 }

문제 해결

function solution(enroll: [string], referral: [string], seller: [string], amount: [number]) {
  const enrollObj = Object.fromEntries(enroll.map((name, idx) => [name, { recommend: referral[idx], money: 0 }]))
  enrollObj['-'] = { recommend: 'no', money: 0 }

  const dfs = (name, money) => {
    // 정지조건
    if (name === '-') {
      enrollObj[name].money += money
      return
    } else {
      // 추천인 찾기
      const recommendPerson = enrollObj[name].recommend
      // 10% 계산, 내림, 1미만 예외처리
      const tenPercent = Math.floor(money / 10)

      enrollObj[name].money += money - tenPercent
      if (tenPercent < 1) return
      dfs(recommendPerson, tenPercent)
    }
  }
  seller.forEach((name, idx) => {
    const money = amount[idx] * 100
    dfs(name, money)
  })

  const answer = Object.entries(enrollObj).map((e) => e[1].money)
  answer.pop()
  return answer
}

느낀점

• 재귀함수 depth 때문에 시간초과와 런타임 에러: 이 문제는 예외처리를 제대로 안해서 발생했다.

  10%를 계산한 금액이 1 원 미만인 경우에는 이득을 분배하지 않고 자신이 모두 가집니다.

이렇게 DFS를 탈출하는 조건을 눈여겨 봐야겠다.

const dfs = (name, money) => {
   ...
      if (tenPercent < 1) return
      dfs(recommendPerson, tenPercent)
    }
  }

• 문제를 푸는 시간을 좀 더 줄여야 겠다.