C++에서 크기가 n인 배열이 n 레벨의 BST를 나타낼 수 있는지 확인하는 방법

문제 개요

배열 A가 주어졌을 때, 이 배열이 n개의 레벨(level)을 가진 BST(이진 탐색 트리)를 나타낼 수 있는지 확인해야 합니다. 트리를 구성할 때는 일반적인 BST의 규칙을 따릅니다. 즉, 어떤 값 k를 기준으로 k보다 큰 값은 오른쪽으로, k보다 작은 값은 왼쪽으로 이동하여 배치됩니다.

예시

{50, 20, 9, 25, 10}과 {50, 30, 20, 25, 10} 두 개의 리스트가 있다고 가정해 보겠습니다.

첫 번째 리스트는 유효하지 않지만, 두 번째 리스트는 유효합니다.

접근 방법

이 문제는 실제로 BST를 구성한 뒤 높이를 검사하는 방식으로도 해결할 수 있지만, 배열 자체만으로 판별하는 방법이 더 효율적입니다. 배열 기반 접근 방식은 다음과 같습니다.

• 초기화: max = 양의 무한대로 설정하여 허용되는 값의 상한을, min = 음의 무한대로 설정하여 하한을 표시합니다.
• arr[i]부터 arr[n-1]까지의 각 원소에 대해 다음 단계를 반복합니다.
  • arr[i] > arr[i-1]이고, arr[i] > min이며, arr[i] < max를 만족하면 min := arr[i-1]로 갱신합니다.
  • 그렇지 않고 arr[i] > min이며 arr[i] < max를 만족하면 max := arr[i]로 갱신합니다.
  • 어느 조건도 만족하지 않으면 해당 원소는 새로운 레벨에 배치되어야 하므로 반복을 중단합니다.

예제 코드

#include <iostream>
using namespace std;
bool canMakeBSTifHeightN(int arr[], int n) {
    int min = INT_MIN;
    int max = INT_MAX;
    for(int i = 1; i < n; i++){
        if (arr[i] > arr[i - 1] && arr[i] > min && arr[i] < max) {
            min = arr[i - 1];
        } else if (arr[i] < arr[i - 1] && arr[i] > min && arr[i] < max) {
            max = arr[i - 1];
        } else {
            return true;
        }
    }
    return false;
}
int main() {
    int elements[] = {50, 30, 20, 25, 10};
    int n = sizeof(elements)/sizeof(elements[0]);
    if (canMakeBSTifHeightN(elements, n))
        cout << "We can make BST of height " << n;
    else
        cout << "We can not make BST of height " << n;
}

실행 결과

We can make BST of height 5

위 예제에서는 배열 {50, 30, 20, 25, 10}이 5개 레벨을 가진 BST로 구성될 수 있는지 검사하며, 조건을 만족하므로 "We can make BST of height 5"가 출력됩니다.