두 개의 배열이 있을 때, 각 배열의 요소를 왼쪽에서 오른쪽 순서대로 삽입하여 이진 탐색 트리(BST)를 만든다고 가정해 봅시다. 이때 두 배열이 동일한 BST를 형성하는지 확인해야 합니다. 단, 실제로 트리를 구축해서는 안 된다는 제약 조건이 있습니다.
예를 들어 배열 {2, 4, 1, 3}과 {2, 1, 4, 3}이 있다면, 두 시퀀스 모두 같은 BST를 만들 수 있습니다.
접근 방법
BST의 기본 성질을 활용하면 됩니다. 왼쪽 서브트리의 모든 요소는 루트보다 작고, 오른쪽 서브트리의 모든 요소는 루트보다 큽니다.
따라서 두 배열이 같은 BST를 나타내기 위한 조건은 다음과 같습니다.
- 각 요소 x에 대해, x의 왼쪽·오른쪽 서브트리에 속한 요소들은 두 배열 모두에서 x보다 뒤에 등장해야 합니다.
- 왼쪽 서브트리와 오른쪽 서브트리의 루트 역시 같은 방식으로 비교합니다.
즉, 주어진 범위(min, max) 내에서 두 배열에서 다음으로 등장하는 요소가 서로 같은지 검사하고, 이 과정을 왼쪽 서브트리와 오른쪽 서브트리에 대해 재귀적으로 반복하면 됩니다.
C++ 구현 예제
#include <iostream>
using namespace std;
bool isSameCheckHelper(int tree1[], int tree2[], int n, int i1, int i2, int min, int max) {
int j, k;
// 첫 번째 배열에서 범위(min, max)에 해당하는 다음 요소 찾기
for (j = i1; j < n; j++)
if (tree1[j] > min && tree1[j] < max)
break;
// 두 번째 배열에서 범위(min, max)에 해당하는 다음 요소 찾기
for (k = i2; k < n; k++)
if (tree2[k] > min && tree2[k] < max)
break;
// 부모 노드가 양쪽 배열 모두에서 리프인 경우
if (j == n && k == n)
return true;
// 한쪽만 존재하거나 값이 다르면 동일한 BST가 아님
if (((j == n) ^ (k == n)) || tree1[j] != tree2[k])
return false;
// 오른쪽 서브트리와 왼쪽 서브트리를 재귀적으로 검사
return isSameCheckHelper(tree1, tree2, n, j + 1, k + 1, tree1[j], max) &&
isSameCheckHelper(tree1, tree2, n, j + 1, k + 1, min, tree1[j]);
}
bool areBSTSame(int first[], int second[], int n) {
return isSameCheckHelper(first, second, n, 0, 0, INT_MIN, INT_MAX);
}
int main() {
int first[] = {8, 3, 6, 1, 4, 7, 10, 14, 13};
int second[] = {8, 10, 14, 3, 6, 4, 1, 7, 13};
int n = sizeof(first) / sizeof(first[0]);
if (areBSTSame(first, second, n)) {
cout << "Two BSTs are same";
} else {
cout << "Two BSTs are not same";
}
}실행 결과
Two BSTs are same
동작 원리 정리
- 현재 검사 중인 범위(min, max) 안에서 각 배열에서 처음으로 등장하는 요소를 찾습니다. 이 요소는 해당 서브트리의 루트입니다.
- 두 배열에서 찾은 요소가 없다면(둘 다 리프), true를 반환합니다.
- 한쪽 배열에만 요소가 있거나, 찾은 두 요소의 값이 다르면 false를 반환합니다.
- 값이 같다면, 그 값을 새로운 경계로 사용하여 오른쪽 서브트리(tree1[j]보다 큰 값)와 왼쪽 서브트리(tree1[j]보다 작은 값)를 각각 재귀적으로 검사합니다.
이 알고리즘의 시간 복잡도는 최악의 경우 O(n²)이며, 공간 복잡도는 재귀 호출 스택으로 인해 O(n)입니다. 실제로 트리 객체를 생성하지 않고 배열의 순서 정보만으로 판별할 수 있다는 점이 핵심입니다.