C++로 구현하는 n-ary 트리에서 주어진 값보다 큰 노드 개수 세기

n-ary 트리와 하나의 숫자가 주어졌을 때, 해당 숫자보다 큰 값을 가진 노드의 개수를 세는 문제입니다. 트리를 순회하면서 조건에 맞는 노드만 카운트하면 되므로, 재귀 호출을 활용하면 간단하게 해결할 수 있습니다.

먼저 예제를 통해 문제를 이해해 보겠습니다.

입력

tree = [[4], [1, 2], [3, 5]]
n = 2

출력

3

위 트리에서 값이 2(n)보다 큰 노드는 3개입니다.

알고리즘

• n-ary 트리를 초기화합니다.

• 카운트 변수를 0으로 초기화합니다.

• 현재 노드의 값이 n보다 크면 카운트를 1 증가시킵니다.

• 현재 노드의 모든 자식 노드를 가져옵니다.

• 각 자식 노드에 대해 동일한 함수를 재귀적으로 호출하여 카운트를 누적합니다.

• 최종 카운트를 반환합니다.

C++ 구현

다음은 위 알고리즘을 C++로 구현한 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    vector<Node*> child;
};
Node* getNewNode(int data) {
    Node* temp = new Node;
    temp->data = data;
    return temp;
}
int getGreaterElementsCount(Node* root, int n) {
    if (root == NULL)
        return 0;
    int count = 0;
    if (root->data > n) {
        count++;
    }
    int nodeChildrenCount = root->child.size();
    for (int i = 0; i < nodeChildrenCount; i++) {
        Node* child = root->child[i];
        count += getGreaterElementsCount(child, n);
    }
    return count;
}
int main() {
    Node* root = getNewNode(1);
    (root->child).push_back(getNewNode(2));
    (root->child).push_back(getNewNode(3));
    (root->child).push_back(getNewNode(4));
    (root->child[0]->child).push_back(getNewNode(5));
    (root->child[0]->child).push_back(getNewNode(5));
    (root->child[1]->child).push_back(getNewNode(6));
    (root->child[1]->child).push_back(getNewNode(6));
    (root->child[1]->child).push_back(getNewNode(7));
    (root->child[2]->child).push_back(getNewNode(8));
    (root->child[2]->child).push_back(getNewNode(8));
    (root->child[2]->child).push_back(getNewNode(9));
    int n = 2;
    cout << getGreaterElementsCount(root, n) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

10

동작 원리 및 복잡도 분석

이 코드는 루트 노드부터 시작해 트리 전체를 깊이 우선 방식으로 순회합니다. 각 노드를 방문할 때마다 해당 노드의 값이 n보다 큰지 확인하고, 그렇다면 카운트를 증가시킨 뒤 자식 노드들에 대해 재귀적으로 같은 작업을 반복합니다.

이 예제에서 값이 2보다 큰 노드는 3, 4, 5, 5, 6, 6, 7, 8, 8, 9로 총 10개이므로 출력값이 10이 됩니다.

시간 복잡도는 트리의 모든 노드를 한 번씩 방문하므로 O(N)(N은 전체 노드 수)입니다. 공간 복잡도는 재귀 호출 스택의 깊이에 비례하여 최악의 경우 O(H)(H는 트리의 높이)입니다.