이 문제에서는 정수 요소로 구성된 배열 arr[]가 주어지며, 우리의 과제는 같은 배열 안에서 각 요소의 Floor(바닥) 값을 찾는 프로그램을 작성하는 것입니다. 특정 요소의 floor가 존재하면 그 값을 출력하고, 존재하지 않으면 -1을 출력합니다.
배열에서 요소의 Floor란, 배열 내에서 해당 요소보다 작거나 같은 값 중 가장 가까운(즉, 가장 큰) 요소를 의미합니다.
문제 이해를 위한 예시
입력과 출력의 관계를 살펴보면 다음과 같습니다.
입력: arr[] = {3, 1, 5, 7, 8, 2}
출력: 2 -1 3 5 7 1예를 들어 첫 번째 요소 3의 floor는 배열에서 3보다 작거나 같은 값 중 가장 큰 2이고, 두 번째 요소 1은 배열에서 자신보다 작은 값이 없으므로 -1이 출력됩니다.
해결 접근 방법
방법 1: 중첩 반복문 사용
배열의 각 요소를 순회하는 외부 반복문과, 해당 요소의 floor를 찾기 위해 배열 전체를 다시 탐색하는 내부 반복문을 사용하는 방식입니다. 구현이 간단하지만 시간 복잡도가 O(n²)이므로 배열이 클 경우 비효율적입니다.
방법 2: 정렬된 배열과 이진 탐색 활용
원본 배열을 정렬한 복사본을 추가로 만든 뒤, 원본 배열의 각 요소에 대해 정렬된 배열에서 이진 탐색(binary search)을 수행하여 floor를 찾는 방식입니다. 시간 복잡도가 O(n log n)으로 훨씬 효율적이며, 아래 예제 코드에서 이 방법을 사용합니다.
예제 코드
다음은 위 해결 방법의 동작을 보여주는 C++ 프로그램입니다.
#include <bits/stdc++.h>
using namespace std;
void printFloorEle(int arr[], int n){
vector<int> sortedArr(arr, arr + n);
sort(sortedArr.begin(), sortedArr.end());
for (int i = 0; i < n; i++) {
if (arr[i] == sortedArr[0]) {
if (arr[i] == sortedArr[1])
cout<<arr[i];
else
cout<<-1;
cout<<"\t";
continue;
}
auto iterator = lower_bound(sortedArr.begin(),sortedArr.end(), arr[i]);
if (iterator != sortedArr.end() && *(iterator + 1) == arr[i])
cout<<arr[i]<<"\t";
else
cout<<*(iterator - 1)<<"\t";
}
}
int main(){
int arr[] = { 3, 1, 5 ,7, 8, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The Floor of every element of the given array is ";
printFloorEle(arr, n);
return 0;
}
코드 설명
- 먼저 원본 배열을 복사해 sortedArr를 만들고 오름차순으로 정렬합니다.
- 각 요소에 대해 lower_bound() 함수로 정렬된 배열에서 해당 값 이상이 처음 나타나는 위치를 찾습니다.
- 탐색 대상이 정렬 배열의 최솟값이라면 그 앞에 더 작은 값이 없으므로, 중복된 값이 있는 경우에만 자기 자신을 floor로 출력하고 없으면 -1을 출력합니다.
- 일반적인 경우에는 lower_bound 결과 바로 앞에 있는 요소, 즉 자신보다 작은 값 중 가장 큰 값이 floor가 됩니다. 단, 동일한 값이 둘 이상 존재하면 자기 자신이 floor가 됩니다.
실행 결과
The Floor of every element of the given array is 2 -1 3 5 7 1