n-ary 트리와 숫자가 주어지면 주어진 숫자보다 큰 노드의 수를 계산해야 합니다. 예를 들어 보겠습니다.
입력
tree = [[4], [1, 2], [3, 5]] n = 2
출력
3
n보다 큰 값을 가진 3개의 노드가 있습니다.
알고리즘
-
n-ary 트리를 초기화합니다.
-
카운트를 0으로 초기화합니다.
-
값이 n보다 큰 노드를 찾으면 카운트를 1씩 증가시킵니다.
-
현재 노드의 자식을 가져옵니다.
-
모든 자식에 대해 반복하고 동일한 함수를 재귀적으로 호출하여 노드를 계산합니다.
-
카운트를 반환합니다.
구현
다음은 위의 알고리즘을 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