Portfolio

You are given a tree (i.e. a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. The root of the tree is the node 0, and each node of the tree has a label which is a lower-case character given in the string labels (i.e. The node with the number i has the label labels[i]).

The edges array is given on the form edges[i] = [ai, bi], which means there is an edge between nodes ai and bi in the tree.

Return an array of size n where ans[i] is the number of nodes in the subtree of the ith node which have the same label as node i.

A subtree of a tree T is the tree consisting of a node in T and all of its descendant nodes.

풀이

재영

첫 번째 방법

💡

메모리 초과.


const countSubTrees = (n, edges, labels) => {
  const result = new Array(n).fill(''); // 결과값들을 캐싱한 거
	// [[0의 나와 자식을 포함한 총라벨들], [1의 ...], [2의], ...]	
  const visited = new Array(n).fill(false); // 방문여부

  const graph = Array.from({ length: n }, () => []); // 간선 정보

  edges.forEach(([from, to]) => {
    graph[from].push(to);
    graph[to].push(from);
  });

  const dfs = (root, res = '') => {
    visited[root] = true;
    const rootChildren = graph[root];

    const label = labels[root];
    res += label; // "내 라벨"

    if (!rootChildren.length) {
      result[root] = res;
      return;
    }

    for (let i = 0; i < rootChildren.length; i += 1) {
      const nowNode = rootChildren[i];
      if (visited[nowNode]) continue;

      dfs(nowNode, '');
      res += result[nowNode]; // result = 자식 노드의 res 캐싱값 배열
    }

    result[root] = res;
  };

  dfs(0);

  return result.map(
    (v, idx) => v.match(new RegExp(labels[idx], 'g'))?.length ?? 0
  );
};

2번째 풀이.

원인은, 모든 결과값을 상위 배열에서 갖고 있기 때문 - 공간복잡도 O(N^2)

따라서 함수 컨텍스트 상에서의 바텀-업 방식으로 해결하자.

결과적으로 맨 아래의 리프의 레이블 수는 항상 1임을 보장 - 1을 카운트하되, 상위 노드에서 이를 채갈 수 있게 하면 된다.

💡

58/59에서 시간초과. 😖


/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {string} labels
 * @return {number[]}
 * @see: https://leetcode.com/problems/number-of-nodes-in-the-sub-tree-with-the-same-label/
 */
const countSubTrees = (n, edges, labels) => {
  const result = new Array(n).fill(0);
  const visited = new Array(n).fill(false);

  const graph = Array.from({ length: n }, () => []);

  edges.forEach(([from, to]) => {
    graph[from].push(to);
    graph[to].push(from);
  });

  const dfs = (root, res = '') => {
    visited[root] = true;
    const rootChildren = graph[root];

    const label = labels[root];
    res += labels[root];

    if (!rootChildren.length) {
      result[root] = 1;
      return res;
    }

    for (let i = 0; i < rootChildren.length; i += 1) {
      const nowNode = rootChildren[i];
      if (visited[nowNode]) continue;

      res += dfs(nowNode);
    }

    result[root] = res.match(new RegExp(label, 'g')).length;
    return res;
  };

  dfs(0);

  return result;
};

{
  const n = 7;
  const edges = [
    [0, 1],
    [0, 2],
    [1, 4],
    [1, 5],
    [2, 3],
    [2, 6],
  ];
  const labels = 'abaedcd';

  console.log(countSubTrees(n, edges, labels));
}

{
  const n = 4;
  const edges = [
    [0, 2],
    [0, 3],
    [1, 2],
  ];
  const labels = 'aeed';

  console.log(countSubTrees(n, edges, labels));
}

3번째 해결

생각해보니 문자열은 상위로갈 수록 거의 100000에 가까워져 간다.

이를 정규표현식으로 탐색하는 것 자체가 O(N)이 추가로 들어가기 때문에 시간 복잡도가 최악의 경우 O(N^2)로 높아진다.

이를 Map을 사용하여 해결하면 어떨까.

이는 O(N * 26)만큼 시간을 절약할 수 있다.


/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {string} labels
 * @return {number[]}
 * @see: https://leetcode.com/problems/number-of-nodes-in-the-sub-tree-with-the-same-label/
 */
const countSubTrees = (n, edges, labels) => {
  const result = new Array(n).fill(0);
  const visited = new Array(n).fill(false);

  const graph = Array.from({ length: n }, () => []);

  edges.forEach(([from, to]) => {
    graph[from].push(to);
    graph[to].push(from);
  });

  const dfs = (root, res = new Map()) => {
    visited[root] = true;
    const rootChildren = graph[root];

    const label = labels[root];
    res.set(labels[root], (res.get(labels[root]) ?? 0) + 1);

    if (!rootChildren.length) {
      result[root] = 1;
      return res;
    }

    for (let i = 0; i < rootChildren.length; i += 1) {
      const nowNode = rootChildren[i];
      if (visited[nowNode]) continue;

      dfs(nowNode).forEach((val, key) => {
        res.set(key, (res.get(key) ?? 0) + val);
      });
    }

    result[root] = res.get(label);
    return res;
  };

  dfs(0);

  return result;
};

{
  const n = 7;
  const edges = [
    [0, 1],
    [0, 2],
    [1, 4],
    [1, 5],
    [2, 3],
    [2, 6],
  ];
  const labels = 'abaedcd';

  console.log(countSubTrees(n, edges, labels));
}

{
  const n = 4;
  const edges = [
    [0, 2],
    [0, 3],
    [1, 2],
  ];
  const labels = 'aeed';

  console.log(countSubTrees(n, edges, labels));
}

결과가 만족스럽지는 않다.

다만 오늘 너무 눈이 아파서 이걸로 만족하려 한다 😖

Number of Nodes in the Sub-Tree With the Same Label

풀이

첫 번째 방법

2번째 풀이.

3번째 해결