서로 다른 개수의 요소를 가진 두 배열이 있다고 가정해 보겠습니다. 우리가 찾아야 하는 것은 쌍 (x, y)입니다. 여기서 x는 첫 번째 배열에 있는 값이고, y는 두 번째 배열에 있는 값입니다. 이 두 요소를 배열 간에 서로 교환했을 때 두 배열의 합이 같아지도록 쌍을 선택해야 합니다.
예를 들어, 첫 번째 배열 A가 [4, 1, 2, 2, 1, 1]을 담고 있고, 두 번째 배열 B가 [3, 3, 6, 3]을 담고 있다고 합시다. 이때 A의 합은 11, B의 합은 15입니다. 여기서 (1, 3)이라는 쌍을 선택하여 두 값을 서로 교환하면 다음과 같이 됩니다.
- 배열 A: [4, 3, 2, 2, 1, 1] → 합계 13
- 배열 B: [1, 3, 6, 3] → 합계 13
두 배열의 합이 13으로 동일해지므로 (1, 3)이 정답 쌍이 됩니다.
접근 방식
이 문제를 해결하는 가장 직관적인 방법은 브루트 포스(Brute Force) 탐색입니다. 첫 번째 배열의 각 요소와 두 번째 배열의 각 요소로 만들 수 있는 모든 쌍을 순회하면서, 해당 쌍을 교환했을 때의 새로운 합을 계산하고 두 값이 일치하는지 비교합니다.
수학적으로 표현하면, A[i]와 B[j]를 교환한 후의 합은 다음과 같습니다.
- 새로운 A의 합 = sumA - A[i] + B[j]
- 새로운 B의 합 = sumB - B[j] + A[i]
두 식이 같아지는 지점을 찾으면 그때의 A[i], B[j]가 바로 원하는 교환 쌍입니다. 이 방법의 시간 복잡도는 두 중첩 반복문 때문에 O(n × m)입니다.
C++ 구현 예제
#include<iostream>
using namespace std;
int arraySum(int arr[], int n) {
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
return sum;
}
void getPair(int A[], int n, int B[], int m) {
int sum_first = arraySum(A, n);
int sum_second = arraySum(B, m);
int newsum_first, newsum_second, first, second;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
newsum_first = sum_first - A[i] + B[j];
newsum_second = sum_second - B[j] + A[i];
if (newsum_first == newsum_second) {
first = A[i];
second = B[j];
}
}
}
cout << "(" << first << ", " << second << ")";
}
int main() {
int A[] = { 4, 1, 2, 2, 1, 1 };
int n = sizeof(A) / sizeof(A[0]);
int B[] = { 3, 3, 6, 3 };
int m = sizeof(B) / sizeof(B[0]);
getPair(A, n, B, m);
}실행 결과
(1, 3)
위 코드는 먼저 arraySum() 함수로 각 배열의 전체 합을 미리 계산합니다. 이후 getPair() 함수에서 이중 반복문을 사용해 모든 가능한 쌍 (A[i], B[j])을 검사하며, 교환 후 두 배열의 합이 같아지는 조합을 발견하면 해당 값을 저장합니다. 최종적으로 조건을 만족하는 쌍 (1, 3)이 출력됩니다.
참고로, 성능을 더 개선하고 싶다면 해시 셋(HashSet)을 활용할 수 있습니다. 목표 차이(diff = (sumB - sumA) / 2)를 먼저 구한 뒤, 두 번째 배열의 값을 해시 셋에 저장하고 첫 번째 배열의 각 요소에 대해 '요소 + diff'가 존재하는지만 확인하면 O(n + m) 시간에 문제를 해결할 수 있습니다.