문제 소개
양수와 음수 노드가 섞여 있는 하나의 이진 트리가 주어졌다고 가정해 보겠습니다. 우리가 해야 할 일은 트리의 각 레벨(층)에 존재하는 노드 값들을 모두 곱한 뒤, 그 결과 중 가장 큰 값을 찾는 것입니다.
위 트리를 예로 들어 보면, 레벨 0의 곱은 4이고, 레벨 1의 곱은 2 × (-5) = -10이며, 레벨 2의 곱은 (-1) × 3 × (-2) × 6 = 36입니다. 따라서 이 트리에서 최대 레벨 곱은 36이 됩니다.
해결 접근 방식
이 문제는 레벨 순서 순회(Level Order Traversal), 즉 너비 우선 탐색(BFS)으로 효율적으로 해결할 수 있습니다. 큐(queue)를 사용해 트리를 한 레벨씩 순회하면서, 같은 레벨에 속한 노드들은 하나의 그룹으로 묶어 처리합니다. 각 레벨마다 노드 값들의 곱을 계산하고, 지금까지 구한 최댓값과 비교하여 더 큰 값으로 갱신하면 됩니다.
알고리즘의 동작 순서는 다음과 같습니다.
- 루트 노드를 큐에 넣고 순회를 시작합니다.
- 큐에 들어 있는 노드 수만큼 반복하며 해당 레벨의 모든 노드를 꺼내고, 그 값들을 서로 곱합니다.
- 노드를 처리하는 동안 자식 노드가 존재하면 큐에 추가하여 다음 레벨을 준비합니다.
- 각 레벨의 곱을 현재까지의 최댓값과 비교해 필요하면 갱신합니다.
- 큐가 빌 때까지 위 과정을 반복한 후 최종 최댓값을 반환합니다.
예제 코드
#include<iostream>
#include<queue>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
};
Node* getNode(int data) {
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
int getMaxLevelProduct(Node* root) {
if (root == NULL)
return 0;
int res = root->data;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int count = q.size();
int prod = 1;
while (count--) {
Node* temp = q.front();
q.pop();
prod *= temp->data;
if (temp->left != NULL)
q.push(temp->left);
if (temp->right != NULL)
q.push(temp->right);
}
res = max(prod, res);
}
return res;
}
int main() {
Node* root = getNode(4);
root->left = getNode(2);
root->right = getNode(-5);
root->left->left = getNode(-1);
root->left->right = getNode(3);
root->right->left = getNode(-2);
root->right->right = getNode(6);
cout << "Maximum level product is " << getMaxLevelProduct(root) << endl;
}
실행 결과
Maximum level product is 36
프로그램을 실행하면 각 레벨의 곱 중 가장 큰 값인 36이 출력됩니다. 이는 앞서 살펴본 레벨 2의 노드 값들을 곱한 결과와 일치합니다.
복잡도 및 정리
이 알고리즘은 트리의 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 또한 큐에는 어느 순간이든 최대 한 레벨의 노드만 저장되므로, 공간 복잡도는 트리의 최대 폭(width)에 비례하는 O(w)입니다. 음수 노드가 포함된 경우에도 단순히 곱셈을 수행하면 되기 때문에 별도의 추가 처리 없이 동일한 로직으로 문제를 해결할 수 있습니다.