[CodeKata] 프로그래머스 : 6.19(토), 다단계 칫솔 판매 / 단어 변환

🥋 Oooth More!! (Level 3) : 다단계 칫솔 판매

문제가 길지만 그림을 보면 이해하기 편하다. 트리 기반 문제로, enroll과 referral 배열끼리 대칭되며 하위-상위 요소의 관계가 성립된다.

seller와 amount 배열도 대칭되며, amount는 판매한 수량이므로 map() 을 통해 *100 을 하여 가격으로 만들어주면 좋을 것 같다.

마지막으로, seller의 각 요소들부터 트리를 타고 올라간다. 상위에 10%, 본인은 90%를 분배하는 식으로 최상위 노드까지 올라간다.

이렇게 했을 때, 트리의 모든 노드들(enroll) 개개인의 수입의 총합이 얼마인지를 계산하면 된다.

 

🧮  풀이

DFS의 방법으로 풀어보았으나, 케이스 10~12번에서 런타임 에러 및 시간초과가 발생하여 개선된 방법을 찾아 해석했다.

function solution(enroll, referral, seller, amount) {
  amount = amount.map(n => n*100);
  let enrollObj = {};
  enroll.forEach(name => enrollObj[name] = { above: '', total: 0 })
  
  function dfs(name, price) {
    const pay = Math.floor(price * 0.1);
    enrollObj[name].total += price - pay;
    if (enrollObj[name].above === "-") {
      return;
    }
    if (enrollObj[name].above) {
      dfs(enrollObj[name].above, pay);
    }
    else {
      const nowAbove = referral[enroll.indexOf(name)];
      enrollObj[name].above = nowAbove
      if (nowAbove !== "-") {
        dfs(nowAbove, pay)
      }
    }
  }

  for (let i = 0 ; i < seller.length ; i++) {
    dfs(seller[i], amount[i])
  }
  
  return Object.values(enrollObj).map(person => person.total);
}

 

🖇 리뷰

function solution(enroll, referral, seller, amount) {
  const tree = {}
  tree['-'] = { parent: null, reward: 0 }

  for (let i = 0; i < enroll.length; i++)
    tree[enroll[i]] = { parent: referral[i], reward: 0 }

  const bottomUp = (name, reward) => {
    const current = tree[name]
    if (!reward || !current.parent) return
    const rewardForParent = Math.floor(reward / 10)
    current.reward += reward - rewardForParent
    bottomUp(current.parent, rewardForParent)
  }

  for (let i = 0; i < seller.length; i++) {
    bottomUp(seller[i], amount[i] * 100)
  }

  return enroll.map(name => tree[name].reward)
}

* 출처 : https://www.cckn.dev/problem-solve/20210427-3/

1. tree 객체에 enroll 요소들의 정보를 저장한다. parent는 부모 요소를 referral에서 찾고, reward는 보상값을 계산하기 위함이다.
2. bottomUp() 함수는 일종의 DFS다. tree 요소(current = tree[name])의 부모가 없거나 reward가 0이면 return 된다.
3. 아니라면, reward를 나눈다. 먼저, rewardForParent를 Math.floor() 로 구하고, 나머지값은 current의 reward에 더한다.
4. 그리고, bottomUp() 함수를 재귀로 실행한다. 인자는 current.parent, rewardForParent를 각각 넘겨준다.
5. 이렇게 세팅한 bottomUp() 함수를, seller의 모든 경우를 순회하면서 실행하면된다. 이때, amount는 *100 해서 가격으로 넣는다. 

나와 같은 방법이었지만 tree['-']까지 설정한 점, 여기서 parent를 null로 막을 수 있고 reward가 0일때도 종료하면서 효율성을 높인 점을 착안해야겠다.

---

🥋 Oooth More!! (Level 3) : 단어 변환

 

🧮  풀이

function solution(begin, target, words) {
  const l = begin.length;
  let answer = Infinity
  
  function dfs(now, count, resWords) {
    if (now === target) {
      answer = Math.min(answer, count)
    }
    count = count + 1;
    for (let w of resWords) {
      let check = 0;
      for (let i = 0 ; i < l ; i++) {
        if (w[i] === now[i]) check++;
      }
      if (check === l-1) {
        dfs(w, count, resWords.filter(word => word !== w))
      }
    }
  }
  
  dfs(begin, 0, words)
  
  return answer === Infinity ? 0 : answer;
}

1. 이문제도 dfs로 풀 수 잇었다. words 모든글자 길이가 같으므로 l로 단순화, answer는 최소 변환횟수를 저장할 변수다.
2. dfs의 인자는 now(현재의 단어), count(변환횟수), resWords(사용가능한 words만 남긴 배열)를 받는다.
3. now가 target 단어와 같다면 종료조건이다. 이 때, answer를 현재값과 지금의 count 중 최소값으로 최신화한다.
4. 종료조건이 아니라면, count를 1 증가시킨다. 그리고, resWords를 순회하며 모든 단어들을 now 단어와 비교한다.
5. check가 l보다 1 작으면 1자리만 빼고 모든 글자가 같은 것이다. 이 때, dfs를 다시 실행시키는 것이다. 여기서 dfs 매개변수로 w(1자리만 같은 단어), count(1 증가된 값), 현재 단어(w)만 필터링된 resWords를 인자로 보낸다.
6. 이 dfs는 최초에는 begin, 0(dfs가 시작되는 즉시 1 증가하므로), words 배열을 매개변수로 각각 넣어 실행한다.
7. answer가 여전히 Infinity인 경우, 모든 dfs 가지에서 최종 target에 도달못한 것이다. 이 때는 0을, 아닐 경우엔 answer를 반환한다.

 

🖇 리뷰

대부분 dfs의 풀이를 활용했으며, 단어의 자리수를 좀 더 효율적으로 비교할 수 없을까 했지만, 반복문이던 reduce던 순회는 필수인 듯 하다.