문제 개요
이 문제에서는 n개의 서로 다른 정수로 이루어진 배열이 주어집니다. 우리가 찾아야 할 것은 배열에 있는 두 정수를 더한 값(합) 중에서 가장 많은 빈도로 나타나는 합입니다. 하나의 합이 여러 쌍에서 동일하게 나타날 수 있으며, 최대 빈도를 가지는 답이 여러 개일 경우 해당하는 모든 합을 출력해야 합니다.
입력 예시
Input : array = { 1, 12, 5, 7, 9, 11 }
Output : 16 12설명: 합 16과 12가 각각 두 번씩 나타납니다.
5 + 11 = 16 & 7 + 9 = 16
1 + 11 = 12 & 5 + 7 = 12
접근 방법
이 문제를 해결하기 위한 기본 아이디어는 다음과 같습니다. 배열에서 만들 수 있는 모든 두 원소 쌍의 합을 계산하고, 각 합이 몇 번 발생했는지 세어 준 뒤, 그중 발생 횟수가 가장 많은 합들을 출력하는 것입니다.
효율적인 빈도 계산을 위해 해시 테이블(unordered_map)을 활용합니다. 해시 테이블을 사용하면 각 합의 발생 횟수를 O(1)에 가까운 속도로 갱신할 수 있습니다.
해결 단계
Step 1: 배열의 모든 두 원소 쌍을 순회합니다.
Step 2: 해시 테이블을 사용하여 각 합의 발생 횟수를 카운트합니다.
Step 3: 순회가 끝난 후, 발생 횟수가 최대인 합을 모두 출력합니다.
구현 예제 (C++)
#include <bits/stdc++.h>
using namespace std;
void sumPairs(int a[], int n){
unordered_map<int, int> pairSum;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
pairSum[a[i] + a[j]]++;
}
}
int occur = 0;
for (auto it : pairSum) {
if (it.second > occur) {
occur = it.second;
}
}
for (auto it : pairSum) {
if (it.second == occur)
cout << it.first <<"\t";
}
}
int main(){
int a[] = { 1, 12, 5, 7, 9, 11 };
int n = sizeof(a) / sizeof(a[0]);
cout<<"The sum pairs with max occurrence are : "<<endl;
sumPairs(a, n);
return 0;
}
코드 설명
위 코드의 동작 과정을 살펴보면 다음과 같습니다.
1단계 — 합 계산 및 카운트: 이중 반복문을 통해 배열의 모든 쌍 (i, j)에 대해 a[i] + a[j] 값을 구하고, unordered_map인 pairSum에 해당 합의 빈도를 1씩 증가시킵니다.
2단계 — 최대 빈도 찾기: 해시 테이블을 순회하며 가장 큰 발생 횟수(occur)를 찾습니다.
3단계 — 결과 출력: 발생 횟수가 occur와 같은 모든 합을 탭 문자로 구분하여 출력합니다. 이렇게 하면 최대 빈도를 가지는 모든 합이 한 번에 출력됩니다.
실행 결과
위 프로그램을 실행하면 다음과 같은 결과를 얻을 수 있습니다.
The sum pairs with max occurrence are −
16 12
시간 복잡도 분석
배열의 크기를 n이라고 할 때, 가능한 모든 쌍의 개수는 n(n−1)/2개이므로 합을 계산하는 데 O(n²)의 시간이 걸립니다. 해시 테이블의 삽입과 조회는 평균적으로 O(1)이므로 전체 시간 복잡도는 O(n²)이며, 공간 복잡도 역시 서로 다른 합의 개수에 비례하여 최대 O(n²)입니다.
마무리
이처럼 해시 테이블을 활용하면 복잡한 정렬 없이도 각 합의 빈도를 손쉽게 추적할 수 있습니다. 주어진 배열에서 최대 빈도로 나타나는 합을 모두 찾아야 하는 유사한 문제(예: 두 수의 차, 곱의 빈도 분석 등)에도 동일한 접근 방식을 응용할 수 있으니 참고하시기 바랍니다.