문제 개요
정수 배열이 하나 주어집니다. 목표는 모든 요소의 합과 해당 요소 자신 사이의 절대 차이가 변수 k보다 큰 요소의 개수를 세는 것입니다.
풀이 아이디어는 간단합니다. 먼저 배열 전체 요소의 합(sum)을 구합니다. 이 합에는 arr[i] 자신도 이미 포함되어 있으므로, 각 요소 arr[i]에 대해 다음 조건을 검사합니다.
sum − 2 × arr[i] > k
조건이 참이면 카운트를 1 증가시키면 됩니다.
예제로 이해하기
예제 1
입력 − arr[] = { 1, 2, 3, 0, 3, 2, 0, 1 }, k = 10
출력 − 요소 개수: 2
설명 − 요소들의 합은 12입니다.
12−1−1=10, 12−2−2=8, 12−3−3=6, 12−0−0=12
절대 차이가 10보다 큰 경우는 12뿐이며, 이는 값이 0인 두 요소에 해당합니다. 따라서 조건을 만족하는 요소는 2개입니다.
예제 2
입력 − arr[] = { 1, 1, 1, 1, 1 }, k = 10
출력 − 요소 개수: 0
설명 − 요소들의 합은 5입니다.
각 요소 1에 대해 5−1−1=3 < 10이므로 조건을 만족하는 요소는 하나도 없습니다.
알고리즘 (프로그램에 사용된 접근 방식)
- 임의의 숫자로 초기화된 정수 배열 arr[]를 준비합니다.
- 함수 numberCount(int arr[], int n, int k)는 배열과 그 길이를 입력으로 받아, 나머지 모든 요소의 합과의 절대 차이가 k보다 큰 요소의 개수를 반환합니다.
- 초기 카운트 값을 0으로 설정합니다.
- 배열의 모든 요소의 합을 계산하여 sum에 저장합니다.
- i = 0부터 i < n까지 배열 전체를 순회합니다.
- 각 요소 arr[i]에 대해 sum − arr[i] − arr[i] > k이면 count를 증가시킵니다.
- 루프가 끝나면 count를 최종 결과로 반환합니다.
예제 코드
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int numberCount(int arr[],int n, int k){
int count=0;
int sum=0;
int i;
for(i=0;i<n;i++)
{ sum+=arr[i]; }
for(int i=0;i<n;i++){
if( abs(sum-arr[i]-arr[i]) > k ){
count++;
}
}
return count;
}
int main(){
int Arr[]={ 1,2,3,4 };
int len=sizeof(Arr)/sizeof(Arr[0]);
int K=5;
cout<<endl<<"Count of elements: "<<numberCount(Arr,len,K);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
Count of elements: 2