이 문제에서는 배열 arr가 주어지며, 배열 안에 K보다 크거나 같은 요소가 최소 K개 존재하는 최대값 K를 찾는 프로그램을 작성하는 것이 목표입니다.
문제 설명
배열에서 "K 이상인 요소의 개수가 K개 이상"이라는 조건을 만족하는 값을 K라고 할 때, 가능한 K 중 가장 큰 값을 구해야 합니다.
예시
입력: arr[] = {3, 5, 1, 7, 6, 6, 4, 8}
출력: 5
설명
배열에서 5보다 크거나 같은 요소는 5, 6, 6, 7, 8로 총 5개입니다. 즉, K = 5일 때 조건을 충족합니다. 반면 K = 6인 경우 6 이상인 요소는 6, 6, 7, 8로 4개뿐이므로 조건을 만족하지 못합니다. 따라서 정답은 5입니다.
해결 접근 방법
가장 간단하고 효과적인 방법은 배열을 오름차순으로 정렬한 뒤, 마지막 인덱스부터 앞쪽으로 순회하면서 조건을 확인하는 것입니다. 인덱스 i에서 자신을 포함한 뒤쪽 요소의 개수는 (N - i)개이므로, arr[i]가 (N - i)보다 작거나 같으면 그 값이 조건을 만족하는 K가 됩니다. 뒤에서부터 탐색하므로 조건을 처음 만족하는 값이 곧 최대 K입니다.
동작 원리
정렬된 배열에서 인덱스 i 이후의 모든 요소는 arr[i]보다 크거나 같기 때문에, (N - i)개의 요소가 모두 arr[i] 이상임이 보장됩니다. 따라서 arr[i] <= (N - i)라면 "arr[i] 이상인 요소가 최소 arr[i]개" 존재한다는 의미가 됩니다.
구현 예제
#include <bits/stdc++.h>
using namespace std;
int CalcMaximumVal(int arr[], int N){
// 배열을 오름차순으로 정렬
sort(arr, arr + N);
// 뒤에서부터 조건 확인
for(int i = (N - 1); i >= 0; i--){
if(arr[i] <= (N - i))
return arr[i];
&;}
return -1; // 조건을 만족하는 K가 없는 경우
}
int main(){
int arr[] = {4, 7, 2, 3, 8};
int N = sizeof(arr) / sizeof(arr[0]);
cout << "배열에 K 이상인 요소가 최소 K개 존재하는 최대값 K는 "
<< CalcMaximumVal(arr, N);
return 0;
}
출력 결과
배열에 K 이상인 요소가 최소 K개 존재하는 최대값 K는 3
실행 과정 분석
입력 배열 {4, 7, 2, 3, 8}을 정렬하면 {2, 3, 4, 7, 8}이 됩니다.
- i = 4 : arr[4] = 8, N - i = 1 → 8 ≤ 1 거짓
- i = 3 : arr[3] = 7, N - i = 2 → 7 ≤ 2 거짓
- i = 2 : arr[2] = 4, N - i = 3 → 4 ≤ 3 거짓
- i = 1 : arr[1] = 3, N - i = 4 → 3 ≤ 4 참 → 3 반환
따라서 결과는 3입니다. 실제로 3 이상인 요소는 3, 4, 7, 8로 4개(≥ 3) 존재하며, 4 이상인 요소는 4, 7, 8로 3개(< 4)이므로 4는 조건을 만족할 수 없습니다.
시간 복잡도
정렬에 O(N log N), 배열 순회에 O(N)이 소요되므로 전체 시간 복잡도는 O(N log N)입니다. 제자리 정렬(in-place sort)을 사용하면 추가 공간 복잡도는 O(1)입니다.