C++로 배열이 비토닉(Bitonic) 배열인지 확인하는 프로그램

N개의 정수로 이루어진 배열 arr[N]이 주어졌을 때, 이 배열이 비토닉(bitonic) 배열인지 판별하는 것이 이번 글의 목표입니다. 배열이 비토닉이라면 "Yes its a bitonic array"를 출력하고, 그렇지 않다면 "No its not a bitonic array"를 출력하면 됩니다.

비토닉 배열이란?

비토닉 배열은 배열의 요소가 먼저 엄격하게 증가하다가, 특정 지점(정점)을 기준으로 엄격하게 감소하는 형태를 가진 배열을 말합니다.

예를 들어 arr[] = {1, 2, 3, 4, 2, -1, -5}는 비토닉 배열입니다. 값이 4에 도달할 때까지는 계속 증가하고, 4 이후에는 계속 감소하기 때문입니다.

입력 예시

arr[] = {1, 3, 5, 4, 2, 0}

출력 결과

Yes its a bitonic array

설명

1 < 3 < 5 > 4 > 2 > 0 이므로 비토닉 배열입니다.

입력 예시

arr[] = {1, 2, 3, 4, 5, 0, -1, -2, 6, -4}

출력 결과

No its not a bitonic array

위 배열은 감소하던 중 다시 6에서 증가하는 구간이 나타나기 때문에 비토닉 배열이 아닙니다.

문제 해결 접근 방법

• 배열의 모든 요소를 순회하면서 이전 요소가 현재 요소보다 작은지(증가 구간인지) 확인합니다.

• 이전 요소가 현재 요소보다 작지 않은 시점이 나타나면 반복을 중단합니다. 이 지점이 정점(peak)입니다.

• 이후 구간에서는 이전 요소가 현재 요소보다 큰지(감소 구간인지) 검사하고, 조건을 벗어나면 false를 반환하며 종료합니다.

• 배열의 끝까지 모든 조건을 통과하면 true를 반환합니다.

알고리즘

Start
Step 1→ 배열의 비토닉 여부를 검사하는 함수 선언
    int check(int arr[], int size)
       int i, j 선언
       Loop For i = 1 and i < size and i++
          IF (arr[i] > arr[i - 1])
             Continue
          End
          IF (arr[i] <= arr[i - 1])
             break
          End
          IF(i == size - 1)
             return 1
          End
          Loop For (j = i + 1 and j < size and j++
             IF (arr[j] < arr[j - 1])
                Continue
             End
             IF (arr[j] <= arr[j - 1])
                break
             End
          End
          Set i = j
          IF (i != size)
             return 0
          End
          return 1
Step 2→ main() 함수에서
    int arr[] = { -3, 9, 11, 20, 17, 5, 1 } 선언
    int size = sizeof(arr) / sizeof(arr[0]) 선언
    (check(arr, size) == 1) ? cout << "Yes its a bitonic array" : cout << "no its not a bitonic array"
Stop

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
// 비토닉 배열 여부를 검사하는 함수
int check(int arr[], int size){
    int i, j;
    // 증가 구간 탐색
    for (i = 1; i < size; i++){
       if (arr[i] > arr[i - 1])
          continue;
       if (arr[i] <= arr[i - 1])
          break;
    }
    if (i == size - 1)
       return 1;
    // 감소 구간 탐색
    for (j = i + 1; j < size; j++){
       if (arr[j] < arr[j - 1])
          continue;
       if (arr[j] >= arr[j - 1])
          break;
    }
    i = j;
    if (i != size)
       return 0;
    return 1;
}
int main(){
    int arr[] = { -3, 9, 11, 20, 17, 5, 1 };
    int size = sizeof(arr) / sizeof(arr[0]);
    (check(arr, size) == 1) ? cout << "Yes its a bitonic array" : cout << "no its not a bitonic array";
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Yes its a bitonic array

입력 배열 {-3, 9, 11, 20, 17, 5, 1}은 20까지 엄격하게 증가한 뒤 1까지 엄격하게 감소하므로, 올바른 비토닉 배열임을 확인할 수 있습니다. 이 알고리즘은 배열을 한 번씩만 순회하므로 시간 복잡도는 O(n)입니다.