정수 배열이 주어졌을 때, 다음 조건을 만족하는 요소의 개수를 구하는 것이 이 문제의 목표입니다.
각 요소에 대해, 배열 안에서 그 요소보다 크거나 같은 숫자의 개수가 정확히 그 요소의 값과 일치해야 합니다(단, 자기 자신은 제외). 즉, 어떤 요소가 X라면 배열에는 X보다 크거나 같은 숫자가 정확히 X개 존재해야 합니다.
입력
Arr[]= { 0,1,2,3,4,9,8 }출력
조건을 만족하는 요소의 개수 : 1
설명 − 각 요소와 그보다 크거나 같은 숫자의 개수는 다음과 같습니다.
Arr[0]: 0보다 크거나 같은 요소 6개, 6!=0 → count=0 Arr[1]: 1보다 크거나 같은 요소 5개, 5!=1 → count=0 Arr[2]: 2보다 크거나 같은 요소 4개, 4!=2 → count=0 Arr[3]: 3보다 크거나 같은 요소 3개, 3==3 → count=1 Arr[4]: 4보다 크거나 같은 요소 2개, 2!=4 → count=1 Arr[5]: 9보다 크거나 같은 요소 0개, 0!=9 → count=1 Arr[6]: 8보다 크거나 같은 요소 1개, 1!=8 → count=1
배열에서 3이 유일하게 조건을 만족하는 요소입니다. 3보다 크거나 같은 요소가 정확히 3개(4, 8, 9) 존재하기 때문입니다.
입력
Arr[]= { 1,1,1,1,1 }출력
조건을 만족하는 요소의 개수 : 0
설명 − 모든 요소가 동일한 값 1이며, 각 요소보다 크거나 같은 다른 요소의 개수는 4개이므로 조건(count==1)을 만족하지 않습니다.
프로그램의 접근 방식
정수 배열 Arr[]에 정수 값들을 저장합니다.
정수형 변수 'n'은 배열의 길이를 저장합니다.
findcount(int arr[], int n) 함수는 배열과 그 크기를 입력으로 받아, 앞서 설명한 조건을 만족하는 숫자의 개수를 반환합니다.
변수 count는 현재 검사 중인 요소보다 크거나 같은 요소의 개수를 임시로 저장합니다.
최종 결과를 담을 변수 ans를 0으로 초기화합니다.
for 루프를 사용하여 첫 번째 요소(인덱스 0)부터 배열 전체를 순회합니다.
내부 for 루프에서는 배열을 다시 처음부터 순회하며, arr[j]>=arr[i]이면서 i!=j인 경우 count를 1씩 증가시킵니다.
내부 루프가 끝나면 count와 arr[i]를 비교합니다. count==arr[i]라면(arr[i]보다 크거나 같은 요소가 정확히 arr[i]개라는 의미) 결과 변수 ans를 증가시킵니다.
모든 루프가 종료되면 'ans'에 저장된 값을 반환합니다.
이 방식은 이중 반복문을 사용하므로 시간 복잡도는 O(n²)입니다. 배열을 미리 정렬(sort)해 두면 비교 연산의 효율성을 높일 수 있습니다.
예제
#include <iostream>
#include <algorithm>
using namespace std;
int findcount(int arr[],int n){
sort(arr,arr+n);
int count=0;
int ans=0;
for(int i=0;i<n;i++){
count=0;
for(int j=0;j<n;j++){
if(arr[j]>=arr[i] && i!=j)
count++;
}
if(count==arr[i])
ans++;
}
return ans;
}
int main(){
int Arr[]= { 0,1,2,3,4,5,6 };
int k=7;
int n=sizeof(Arr)/sizeof(Arr[0]);
std::cout<<"Elements exactly greater than equal to itself : "<<findcount(Arr,n);
return 0;
}출력
Elements exactly greater than equal to itself : 1