정수 요소로 구성된 배열 arr[]와 하나의 정수 num이 주어졌을 때, 각 요소 arr[i]와 num의 평균값을 구하고, 그 평균값이 원래 배열 arr[] 안에서 몇 번 나타나는지 그 횟수를 출력하는 것이 이 문제의 목표입니다.
예를 들어 배열 arr[]가 [5, 2, 3]이고 num이 2라면, 각 평균값은 [3, 2, 2]가 되고, 이 값들이 arr[]에 등장하는 횟수는 [1, 1, 1]입니다.
예시
입력
arr[] = { 1, 6, 4, 3, 6, 4 }
num = 2출력
1 2 1 0 2 1
주어진 숫자와 배열 요소의 평균값이 등장한 총 횟수: 5
설명
num은 2이며, arr[]의 각 요소와의 평균값은 :
[ 1, 4, 3, 2, 4, 3 ] 이 값들이 arr[]에 등장하는 횟수는 [ 1, 2, 1, 0, 2, 1 ]
입력
arr[] = { 4, 8, 24, 16, 20, 40 }
num = 4출력
1 0 0 0 0 0
주어진 숫자와 배열 요소의 평균값이 등장한 총 횟수: 1
설명
num은 4이며, arr[]의 각 요소와의 평균값은 :
[ 4, 6, 14, 10, 12, 22 ] 이 값들이 arr[]에 등장하는 횟수는 [ 1, 0, 0, 0, 0, 0 ]
아래 프로그램에서 사용된 접근 방식
이 접근 방식에서는 원본 배열에 있는 값들과 그 등장 횟수를 저장하기 위한 맵(map)을 생성합니다. 그런 다음 각 평균값의 등장 횟수를 별도의 배열에 저장하여 출력합니다.
정수형 배열 arr[]를 선언합니다.
정수 num을 입력받습니다.
함수 occurrence_average(int arr[], int size, int num)는 입력 배열과 num을 받아 arr[]에서 각 평균값이 등장한 횟수 배열을 출력하고, 0이 아닌 등장 횟수의 개수를 반환합니다.
초기 count 값을 0으로 설정합니다.
arr[]에 있는 고유한 숫자들의 등장 횟수를 저장하기 위해 map<int,int> 타입의 map_pair를 사용합니다.
각 평균값의 등장 횟수를 저장할 배열 total[]을 준비합니다.
인덱스 i=0부터 i<size까지 for 루프로 배열 arr[]를 순회하면서, 각 요소에 대해 map_pair[arr[i]]++로 해당 키의 값을 증가시킵니다.
루프가 종료되면 map에는 고유 숫자가 키로, arr[]에서의 등장 횟수가 값으로 저장됩니다.
배열을 다시 for 루프로 순회하면서 각 요소와 num의 평균을 계산하여 temp에 저장합니다.
map_pair.find(temp) != map_pair.end() 조건으로 temp가 map_pair에 존재하는지 확인하고, 존재한다면 그 등장 횟수를 total 배열에 저장합니다.
arr[]에서 발견된 평균값들의 등장 횟수가 담긴 total 배열을 출력합니다. 이때 0이 아닌 요소마다 count를 증가시킵니다.
count를 결과로 반환합니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
int occurrence_average(int arr[], int size, int num){
int count = 0;
map<int,int> map_pair;
int total[size] = {0};
int val, av;
for (int i = 0; i < size; i++){
if (map_pair[arr[i]] == 0){
map_pair[arr[i]] = 1;
} else {
map_pair[arr[i]]++;
}
}
for (int i = 0; i < size; i++){
int temp = int((arr[i] + num) / 2);
if(map_pair.find(temp) != map_pair.end()){
int set = map_pair[temp];
total[i] = set;
}
}
cout<<endl;
for(int i=0;i<size;i++){
cout<<total[i]<<" ";
if(total[i]>0){
count++;
}
}
return count;
}
int main(){
int arr[] = { 4, 8, 24, 16, 20, 40 };
int size = sizeof(arr)/sizeof(arr[0]);
int num = 4;
cout<<endl<<"주어진 숫자와 배열 요소의 평균값 등장 횟수: "<<occurrence_average(arr, size, num);
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
주어진 숫자와 배열 요소의 평균값 등장 횟수:
1 0 0 0 0 0 1
여기서 마지막에 출력되는 1은 occurrence_average 함수가 반환한 count 값입니다. 즉, 계산된 평균값 중 실제로 배열에 존재하는 경우는 요소 4와 num 4의 평균인 4 하나뿐입니다.
복잡도 분석
시간 복잡도: 맵의 삽입과 검색 연산이 각각 O(log n)이므로, 전체 시간 복잡도는 O(n log n)입니다.
공간 복잡도: 맵과 보조 배열 total[]을 위해 O(n)의 추가 공간이 필요합니다.