정수 배열이 주어지며, 각 원소는 -1000부터 1000 사이의 범위에 있다고 가정합니다. 우리의 목표는 두 원소의 평균값 역시 그 배열 안에 존재하는 원소 쌍(pair)의 개수를 찾는 것입니다.
예를 들어 배열이 arr[] = [1, 2, 3, 4]라면, 조건을 만족하는 쌍은 (1, 3)과 (2, 4)입니다. 1과 3의 평균은 2이고, 2와 4의 평균은 3인데, 2와 3 모두 배열에 존재하기 때문입니다. 따라서 정답은 2가 됩니다.
예제로 이해하기
입력 − arr[] = { -1, 2, 5, -3, 8, 10 }
출력 − 평균이 같은 배열에 존재하는 쌍의 개수 = 2
설명 − (-1, 5)의 평균은 2이고, (2, 8)의 평균은 5입니다. 두 값 모두 배열에 존재하므로 Count = 2입니다.
입력 − arr[] = { 1, 3, 2, 5, 10, 6 }
출력 − 평균이 같은 배열에 존재하는 쌍의 개수 = 3
설명 − (1, 3)의 평균은 2, (1, 5)의 평균은 3, (2, 10)의 평균은 6입니다. 세 값 모두 배열에 존재하므로 Count = 3입니다.
문제 해결 접근 방식
먼저 배열의 모든 원소에 대한 빈도(frequency) 배열을 만듭니다. 빈도 배열의 크기는 음수 원소도 처리해야 하기 때문에 원래 범위의 두 배인 2001로 설정합니다.
음수의 빈도는 인덱스 0부터 1000까지, 양수의 빈도는 인덱스 1000부터 2000까지 기록됩니다. 실제 값에 1000(N)을 더하면 해당 인덱스가 됩니다.
빈도가 0이 아닌 각 인덱스에 대해 다음 규칙을 적용합니다.
같은 숫자끼리의 쌍: freq[i] × (freq[i] − 1) / 2를 count에 더합니다. 같은 숫자 두 개의 평균은 그 숫자 자신이 되기 때문입니다. 예를 들어 배열에 2가 5개 있다면 가능한 쌍은 (5 × 4) / 2 = 10개입니다.
2씩 건너뛰며 탐색: freq[i]가 0이 아니라면, j를 i+2부터 2씩 증가시키며 탐색합니다. 연속된 두 숫자의 평균은 소수가 되어 정수 배열에는 존재할 수 없기 때문입니다.
평균 존재 여부 확인: freq[j]가 0이 아니고 freq[(i + j) / 2]도 0이 아니라면, 두 숫자의 평균이 배열에 존재한다는 뜻입니다. 이때 freq[i] × freq[j]를 count에 더합니다. 각 숫자는 서로 다른 모든 숫자와 짝을 이룰 수 있기 때문입니다.
알고리즘 단계
정수 배열 arr[]와 그 크기를 입력받습니다.
average_pair(arr, size) 함수는 쌍의 평균이 배열 arr[]에도 존재하는 쌍의 개수를 반환합니다.
count를 0으로 초기화하고 N = 1000으로 설정합니다.
빈도 배열의 길이는 size_2 = 2 × N + 1 (범위 [-1000, 1000])로 계산합니다.
빈도 배열 arr_freq를 0으로 초기화합니다.
각 원소 arr[i]에 대해 arr_freq[arr[i] + N]++로 빈도를 갱신합니다. 이렇게 하면 음수는 0~1000, 양수는 1000~2000 인덱스에 기록됩니다.
빈도 배열을 i = 0부터 size_2 미만까지 순회합니다.
빈도가 0이 아닌 경우, 규칙 1에 따라 (freq[i]) × (freq[i] − 1) / 2를 count에 더합니다.
j를 i + 2부터 2씩 증가시키며 탐색하고, temp_2 = arr_freq[(i + j) / 2]를 계산합니다.
temp_2가 0이 아니고 arr_freq[j]도 0이 아니라면 규칙 3이 충족되므로, count에 arr_freq[i] × arr_freq[j]를 더합니다.
모든 반복이 끝나면 count에 조건을 만족하는 쌍의 총 개수가 저장되며, 이 값을 결과로 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int average_pair(int arr[], int size_1){
int count = 0;
int N = 1000;
int size_2 = (2 * N) + 1;
int arr_freq[size_2] = { 0 };
for (int i = 0; i < size_1; i++){
int temp = arr[i];
arr_freq[temp + N]++;
}
for (int i = 0; i < size_2; i++){
if (arr_freq[i] > 0){
int check = (arr_freq[i]) * (arr_freq[i] - 1);
count += check / 2;
for (int j = i + 2; j < 2001; j += 2){
int temp_2 = arr_freq[(i + j) / 2];
if (arr_freq[j] > 0 && temp_2 > 0){
count += (arr_freq[i] * arr_freq[j]);
}
}
}
}
return count;
}
int main(){
int arr[] = { 2, 3, 1, 8, 9, 10 };
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of pairs with average present in the same array are: "<<average_pair(arr, size);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Count of pairs with average present in the same array are: 2
이처럼 빈도 배열을 활용하면 모든 쌍을 일일이 비교하는 O(n²) 완전 탐색보다 효율적으로, 고정된 범위의 정수 배열에서 조건을 만족하는 쌍의 개수를 선형 시간에 가깝게 계산할 수 있습니다.