C++로 정렬되지 않은 배열에서 Floor와 Ceiling 값 찾는 방법

이번 글에서는 정렬되지 않은 배열(unsorted array)에서 floor(바닥값)와 ceiling(천장값)을 찾는 방법을 알아보겠습니다.

먼저 두 개념을 간단히 정리하면 다음과 같습니다.

• Floor 값: x보다 작거나 같은 요소 중에서 가장 큰 값
• Ceiling 값: x보다 큰 값 중에서 가장 작은 값

예를 들어 배열 A = [5, 6, 8, 9, 6, 5, 5, 6]이 있고 x가 7이라고 가정해 봅시다. 이때 floor 값은 6이 되고, ceiling 값은 8이 됩니다.

접근 방법: 선형 탐색 (Linear Search)

이 문제는 선형 탐색 방식으로 해결할 수 있습니다. 배열을 한 번 순회하면서 x를 기준으로 다음 두 가지 거리 값을 추적합니다.

• x보다 크거나 같은 요소 중 최소 거리에 있는 값 (ceiling 후보)
• x보다 작거나 같은 요소 중 최소 거리에 있는 값 (floor 후보)

배열 순회가 끝나면 각각의 조건에 맞는 최소 거리의 요소를 결과로 출력하면 됩니다. 만약 해당하는 값이 존재하지 않으면 "찾을 수 없음" 메시지를 출력합니다.

구현 예제 코드

#include<iostream>
using namespace std;

void floorCeilingPair(int arr[], int n, int x) {
   int floor_index, ceiling_index;
   int floor_dist = INT_MAX, ceil_dist = INT_MAX;
   for (int i = 0; i < n; i++) {
      if (arr[i] >= x && ceil_dist > (arr[i] - x)) {
         ceiling_index = i;
         ceil_dist = arr[i] - x;
      }
      if (arr[i] <= x && floor_dist > (x - arr[i])) {
            floor_index = i;
            floor_dist = x - arr[i];
      }
   }
   if (floor_dist == INT_MAX)
      cout << "Floor not found" << endl;
   else
      cout << "Floor value is " << arr[floor_index] << endl;
   if (ceil_dist == INT_MAX)
      cout << "Ceiling not found" << endl;
   else
      cout << "Ceil value is " << arr[ceiling_index] << endl;
}

int main() {
   int arr[] = {5, 6, 8, 9, 6, 5, 5, 6};
   int n = sizeof(arr) / sizeof(int);
   int x = 7;
   floorCeilingPair(arr, n, x);
}

실행 결과

Floor value is 6
Ceil value is 8

코드 동작 원리

이 알고리즘은 배열의 각 요소를 한 번씩 확인하면서 다음과 같이 동작합니다.

1. 현재 요소가 x보다 크거나 같으면, 기존에 저장된 ceiling 거리(ceil_dist)와 비교하여 더 가까운 값으로 갱신합니다.
2. 현재 요소가 x보다 작거나 같으면, 기존에 저장된 floor 거리(floor_dist)와 비교하여 더 가까운 값으로 갱신합니다.
3. 모든 순회가 끝난 후 거리 값이 여전히 INT_MAX라면 조건을 만족하는 요소가 없었다는 의미이므로, 해당 값은 찾을 수 없다고 출력합니다.

시간 복잡도

이 방법의 시간 복잡도는 O(n)입니다. 배열 전체를 한 번만 순회하기 때문에 효율적이며, 공간 복잡도 역시 추가 배열이 필요하지 않아 O(1)입니다. 배열이 정렬되어 있다면 이진 탐색(Binary Search)을 활용해 O(log n)으로 개선할 수 있지만, 이 예제는 정렬되지 않은 배열을 대상으로 하므로 선형 탐색이 적합합니다.