문제 개요
정수 값으로 구성된 이진 탐색 트리(Binary Search Tree, BST)와 하나의 숫자 total이 주어졌다고 가정해 보겠습니다. 이때 해결해야 할 문제는, 트리에 속한 세 원소의 합이 total과 정확히 일치하는 조합(삼중항, triplet)이 존재하는지 판별하는 것입니다.
예를 들어 다음과 같은 BST가 있고,
total = 12라면, 3 + 4 + 5 = 12처럼 조건을 만족하는 조합이 존재하므로 출력은 True가 됩니다.
해결 접근 방법
이 문제는 중위 순회(inorder traversal)와 투 포인터(two-pointer) 기법을 조합하면 효율적으로 해결할 수 있습니다. 단계별로 살펴보겠습니다.
- 값을 담을 빈 리스트(temp_list)를 준비합니다.
- 트리를 중위 순회하면서 방문한 값을 순서대로 temp_list에 저장합니다. BST의 성질 덕분에 중위 순회 결과는 항상 오름차순으로 정렬된 목록이 됩니다.
- 정렬된 리스트에서 세 수의 합이 total이 되는지 검사합니다.
- 첫 번째 원소의 인덱스 i를 고정하고, 왼쪽 포인터 left는 i + 1, 오른쪽 포인터 right는 리스트의 마지막 인덱스로 설정합니다.
- left < right인 동안 다음을 반복합니다.
- temp_list[i] + temp_list[left] + temp_list[right]가 total과 같으면 True를 반환합니다.
- 합이 total보다 작으면 더 큰 값이 필요하므로 left를 1 증가시킵니다.
- 합이 total보다 크면 더 작은 값이 필요하므로 right를 1 감소시킵니다.
- i를 끝까지 옮겨도 적절한 조합을 찾지 못하면 False를 반환합니다.
구현 예제
아래 파이썬 코드로 위 알고리즘을 직접 구현해 보겠습니다.
class TreeNode:
def __init__(self, value):
self.value = value
self.right = None
self.left = None
def traverse_inorder(tree_root, inorder):
if tree_root is None:
return
traverse_inorder(tree_root.left, inorder)
inorder.append(tree_root.value)
traverse_inorder(tree_root.right, inorder)
def solve(tree_root, target_sum):
temp_list = []
traverse_inorder(tree_root, temp_list)
n = len(temp_list)
for i in range(0, n - 2):
left = i + 1
right = n - 1
while left < right:
current_sum = temp_list[i] + temp_list[left] + temp_list[right]
if current_sum == target_sum:
return True
elif current_sum < target_sum:
left += 1
else:
right -= 1
return False
tree_root = TreeNode(5)
tree_root.left = TreeNode(3)
tree_root.right = TreeNode(7)
tree_root.left.left = TreeNode(2)
tree_root.left.right = TreeNode(4)
tree_root.right.left = TreeNode(6)
tree_root.right.right = TreeNode(8)
print(solve(tree_root, 12))
입력
트리: 루트 5, 왼쪽 자식 3(자식: 2, 4), 오른쪽 자식 7(자식: 6, 8) total = 12
출력
True
복잡도 분석
중위 순회에는 O(n)의 시간이 걸리고, 고정한 각 원소마다 투 포인터 탐색에 최대 O(n)이 소요되므로 전체 시간 복잡도는 O(n²)입니다. 정렬된 값을 저장하는 리스트 때문에 공간 복잡도는 O(n)입니다. 세 원소를 무작정 모두 골라 비교하는 브루트 포스(O(n³)) 방식보다 한 단계 개선된 접근이라는 점이 이 알고리즘의 핵심입니다.