Python으로 배열이 이진 탐색 트리(BST)의 중위 순회(Inorder) 결과인지 확인하는 방법

숫자로 이루어진 배열 nums가 주어졌을 때, 이 배열이 어떤 이진 탐색 트리(Binary Search Tree)를 중위 순회(Inorder Traversal)한 결과와 일치하는지 확인하는 문제입니다.

예를 들어 입력이 nums = [5, 8, 15, 18, 20, 26, 39]라면, 이 배열은 아래 트리를 중위 순회한 결과이므로 출력은 True가 됩니다.

핵심 아이디어

이진 탐색 트리의 가장 중요한 성질 중 하나는 중위 순회를 수행하면 항상 오름차순으로 정렬된 값들이 얻어진다는 것입니다. 따라서 복잡하게 트리를 재구성할 필요 없이, 단순히 배열이 오름차순으로 정렬되어 있는지만 확인하면 됩니다.

풀이 절차

• 배열의 크기를 구합니다.
• 배열의 크기가 0 또는 1이라면 빈 트리 또는 노드 하나짜리 트리로 볼 수 있으므로 True를 반환합니다.
• 인덱스 1부터 마지막 요소까지 반복하면서, 이전 요소가 현재 요소보다 큰 경우(내림차순 구간)가 있다면 False를 반환합니다.
• 모든 검사를 통과하면 배열은 오름차순이므로 True를 반환합니다.

구현 예제

def solve(nums):
    size = len(nums)
    if size == 0 or size == 1:
        return True
    for i in range(1, size):
        if nums[i - 1] > nums[i]:
            return False
    return True

nums = [5, 8, 15, 18, 20, 26, 39]
print(solve(nums))

입력

[5, 8, 15, 18, 20, 26, 39]

출력

True

복잡도 분석

배열을 한 번만 순회하므로 시간 복잡도는 O(n), 추가 공간은 상수만 사용하므로 공간 복잡도는 O(1)입니다. 매우 효율적인 해결 방법입니다.