프로그래머스 타겟 넘버 (Javascript) 풀이, "트리다 트리!"

트리다 트리!!!

• 문제 링크

문제 설명

n개의 음의 아닌 정수를 적절히 더하거나 빼서 타깃 넘버로 만드는 경우를 수를 구하는 문제다.

해결 과정

결국 n 개의 모든 수를 각각 더하거나 뺄 수 있다. 그리고 그 경우의 수를 알고, 그 값들이 타깃 넘버인지 비교해야 한다.

처음에는 어떻게 이 모든 경우를 반복문으로 구한단 말인가? 절망하다가 뭔가 규칙이 느껴지는 듯 했다. 더하거나, 빼거나, 더하거나 빼거나 ... 그리고 그 값은 누적된다.

트리다 트리!!

마치 위와 같은 형태였다. 오오, 이것은 트리였다!

트리의 모든 요소를 다뤄야 하나?

그리고 numbers로 들어온 요소의 수를 더하든 빼든 그 결과만 모아서 확인해야 하는데, 그것은 트리에서 같은 깊이, Level을 들여다보면 됐다.

그렇다면 트리를 어떻게 구현하지?

트리의 특정 레벨만 확인하고 싶을 때 어떻게 해야 할까? 노드(Node) 클래스를 만들고 left와 right를 넣으며 구현을 해야하나 싶었다. 하지만 너무 코드가 길어지고 귀찮을 것 같았다. 어떻게 쉬운 방법이 없을까, 고민했다.

트리인데, 클래스 말고 쓰기 편한 배열로 구현하려면 ...

그때 자료구조에서 배웠던 바이너리 힙이 떠올랐다! 그 중에서 Max Binary Heap은 가장 큰 값이 트리의 최상위에 위치하고 그 아래 있는 것은 항상 부모 노드보다 작다. 자식 간 대소는 상관 없는 자료구조다. 그리고 이 바이너리 힙의 특징은 트리 자료구조임에도 불구하고 배열로 그 구조를 표현할 수 있다는 것이었다!

바이너리 힙...은 아니지만 바이너리 힙처럼 배열로 구현하자!

바이너리힙에서 특정 인덱스(i)에 위치한 노드의 왼쪽 자식 노드는 그 i*2 + 1 인덱스에 위치한다. 오른쪽은 i*2+2다. 이 원칙으로 이 문제에 필요한 트리를 배열로 구현할 수 있다고 판단했다.

그래서 정답은 어떻게?

그런 다음 정답은 트리의 특정 레벨의 모든 값을 가져와서 타깃 넘버가 된 값들을 헤아려야 한다.

k 레벨의 **포화 이진 트리(무조건 더하고 빼서 트리를 만들었으니 포화다!)**의 노드 수는 2의 k제곱이다.

따라서 트리를 담고 있는 배열의 마지막부터 2의 k제곱 부분을 떼낸다. 그 부분에서 타깃넘버가 몇 개인지 세면 된다.

소스 코드

function solution(numbers, target) {
  const container = [0];
  let treeIndex = 0;
  let numIndex = 0;

  function makeTree(treeIndex, numIndex) {
    if (numIndex === numbers.length) {
      return;
    }

    if (container[treeIndex * 2 + 1] === undefined) {
      container[treeIndex * 2 + 1] = container[treeIndex] - numbers[numIndex];
      makeTree(treeIndex * 2 + 1, numIndex + 1);
    }

    if (container[treeIndex * 2 + 2] === undefined) {
      container[treeIndex * 2 + 2] = container[treeIndex] + numbers[numIndex];
      makeTree(treeIndex * 2 + 2, numIndex + 1);
    }
  }

  makeTree(treeIndex, numIndex);

  return container
    .slice(Math.pow(2, numbers.length))
    .filter((num) => num === target).length;
}

---

감상

이렇게 그림을 그려가며 문제를 상상하고, 최근에 배웠던 것을 활용해서 풀었다는 게 신기했고 뿌듯했다. 어렵게만 보였던 트리 관련 문제들을 어떻게든 풀 수 있는 거 아닐까, 희망이 보이는 것 같기도 했다.

참고 자료 및 출처

• https://ko.wikipedia.org/wiki/트리_구조
• https://ko.wikipedia.org/wiki/힙_(자료_구조)