두 개의 이진 탐색 트리(Binary Search Tree, BST)와 값 x가 입력으로 주어졌을 때, 각 트리에서 노드를 하나씩 선택하여 두 노드 값의 합이 x와 같아지는 쌍의 개수를 구하는 것이 목표입니다. 예를 들어 BST_1에서 노드 1을, BST_2에서 노드 2를 가져와 두 데이터 값을 더했을 때 그 합이 x라면 카운트를 1 증가시킵니다.
구체적인 예시를 통해 살펴보겠습니다.
입출력 예시
입력
출력 − 합이 x와 같은 두 BST의 노드 쌍 개수: 1
설명 − 해당하는 쌍은 (8, 6)입니다.
입력
출력 − 합이 x와 같은 두 BST의 노드 쌍 개수: 2
설명 − 해당하는 쌍은 (5, 15)와 (4, 16)입니다.
알고리즘 접근 방법
이 방법에서는 반복적 중위 순회(iterative inorder traversal) 기법을 사용하여 두 개의 BST를 순회합니다. BST 1은 가장 작은 노드부터 가장 큰 노드 방향으로 중위 순회를 진행하고, BST 2는 그 반대 방향으로 순회합니다. 그런 다음 두 BST의 현재 노드 값을 더한 뒤, 그 합이 x와 같으면 카운트를 증가시킵니다. 합이 x보다 크면 BST 2의 현재 노드를 중위 선행자(inorder predecessor)로 이동하고, 합이 x보다 작으면 BST 1의 현재 노드를 중위 후속자(inorder successor)로 이동합니다.
정수 데이터와 왼쪽·오른쪽 자식 포인터를 가지는 두 개의 트리 BST_1과 BST_2를 준비합니다.
insert_node(int data) 함수는 새 데이터를 가진 노드를 트리에 삽입하고 해당 노드의 포인터를 반환합니다.
insert_node() 함수로 두 개의 BST를 생성한 뒤, BST_sum_x(Tree* BST_1, Tree* BST_2, int x)에 전달합니다.
BST_sum_x(Tree* BST_1, Tree* BST_2, int x) 함수는 두 트리의 루트 노드를 받아서, 데이터 합이 x가 되는 노드 쌍의 개수를 반환합니다.
합이 x인 쌍의 개수를 저장할 count 변수를 0으로 초기화합니다.
반복적 중위 순회를 위해 Tree* stack_top_1, *stack_top_2 두 개의 변수를 선언합니다.
스택 두 개(stack_1, stack_2)를 생성합니다.
바깥쪽 while 루프를 시작합니다.
while 루프를 사용해 BST_1의 가장 왼쪽(가장 작은) 노드까지 이동하면서 모든 노드를 stack_1에 push합니다.
while 루프를 사용해 BST_2의 가장 오른쪽(가장 큰) 노드까지 이동하면서 모든 노드를 stack_2에 push합니다.
두 스택 중 하나라도 비어 있으면 바깥쪽 while 루프를 종료(break)합니다.
두 스택의 최상단(top) 노드를 꺼내어 데이터 값을 더한 결과를 temp에 저장합니다.
temp(합) == x라면 count를 증가시키고, pop 연산으로 stack_1과 stack_2에서 각각 최상단 원소를 제거합니다.
BST_1 = stack_top_1->right, BST_2 = stack_top_2->left로 설정합니다(즉, BST_1에서는 다음 후속자로, BST_2에서는 다음 선행자로 이동).
temp < x라면 stack_1의 최상단만 제거하고 BST_1의 다음 후속자로 이동합니다.
temp > x라면 stack_2의 최상단만 제거하고 BST_2의 다음 선행자로 이동합니다.
바깥쪽 while 루프가 끝나면, count에는 두 BST의 노드들 중 합이 x가 되는 쌍의 개수가 저장되어 있습니다.
결과로 count를 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
struct Tree{
int data;
Tree* left, *right;
};
Tree* insert_node(int data){
Tree* newNode = (Tree*)malloc(sizeof(Tree));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
}
int BST_sum_x(Tree* BST_1, Tree* BST_2, int x){
int count = 0;
Tree* stack_top_1, *stack_top_2;
stack<Tree*> stack_1, stack_2;
if (BST_1 == NULL || BST_2 == NULL){
return 0;
}
while (1){
while (BST_1 != NULL){
stack_1.push(BST_1);
BST_1 = BST_1->left;
}
while (BST_2 != NULL){
stack_2.push(BST_2);
BST_2 = BST_2->right;
}
if (stack_1.empty() || stack_2.empty()){
break;
}
stack_top_1 = stack_1.top();
stack_top_2 = stack_2.top();
int temp = stack_top_1->data + stack_top_2->data;
if (temp == x){
count++;
stack_1.pop();
stack_2.pop();
BST_1 = stack_top_1->right;
BST_2 = stack_top_2->left;
}
else if (temp < x){
stack_1.pop();
BST_1 = stack_top_1->right;
}
else{
stack_2.pop();
BST_2 = stack_top_2->left;
}
}
return count;
}
int main(){
// BST 1
Tree* BST_1 = insert_node(15);
BST_1->left = insert_node(10);
BST_1->right = insert_node(8);
BST_1->left->left = insert_node(12);
BST_1->left->right = insert_node(24);
BST_1->right->left = insert_node(16);
// BST 2
Tree* BST_2 = insert_node(20);
BST_2->left = insert_node(16);
BST_2->right = insert_node(4);
BST_2->left->left = insert_node(18);
BST_2->left->right = insert_node(28);
BST_2->right->left = insert_node(22);
int x = 28;
cout<<"합이 x와 같은 두 BST의 노드 쌍 개수: "<<BST_sum_x(BST_1, BST_2, x);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
합이 x와 같은 두 BST의 노드 쌍 개수: 1