이 문제에서는 양수이면서 서로 중복되지 않는 원소로 이루어진 두 개의 배열이 주어집니다. 우리의 목표는 두 배열에서 각각 하나의 원소를 선택해 만들 수 있는 쌍(pair) 중 최대 합을 구하는 것입니다.
즉, 첫 번째 배열에서 하나의 원소를, 두 번째 배열에서 하나의 원소를 뽑아 만들 수 있는 모든 쌍 중에서 합이 가장 큰 값을 찾으면 됩니다.
문제 예시
입력 : arr1[] = {3, 7, 5}, arr2[] = {8, 2, 4}
출력 : 15설명 −
가장 큰 합을 가지는 쌍은 (7, 8) → 7 + 8 = 15
풀이 접근 방법
1. 단순한 방법 — 중첩 반복문 사용
가장 직관적인 방법은 중첩 반복문(nested loop)을 사용하는 것입니다. 첫 번째 배열의 모든 원소와 두 번째 배열의 모든 원소를 조합하며 쌍의 합을 계산하고, 그중 최댓값을 반환합니다. 하지만 이 방법은 시간 복잡도가 O(n1 × n2)로, 배열의 크기가 커지면 비효율적입니다.
2. 효율적인 방법 — 각 배열의 최댓값 활용
두 배열의 원소가 모두 양수라는 조건이 있으므로, 각 배열의 최댓값을 찾아 더하는 것만으로 최대 쌍의 합을 구할 수 있습니다. 단순 반복문 한 번씩만 돌면 되므로 시간 복잡도는 O(n1 + n2)로 매우 효율적입니다.
예제 코드
#include <iostream>
using namespace std;
int findMaxPairSum(int arr1[], int n1, int arr2[], int n2) {
int max1 = -1;
int max2 = -1;
for (int i = 0; i < n1; i++) {
if (arr1[i] > max1)
max1 = arr1[i];
}
for (int i = 0; i < n2; i++) {
if (arr2[i] > max2)
max2 = arr2[i];
}
return (max1 + max2);
}
int main() {
int arr1[] = { 3, 7, 5 };
int arr2[] = { 8, 2, 4 };
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int n2 = sizeof(arr2) / sizeof(arr2[0]);
cout<<"두 배열에서 최대 합을 가지는 쌍의 합은 "<<findMaxPairSum(arr1, n1, arr2, n2);
return 0;
}
출력 결과
두 배열에서 최대 합을 가지는 쌍의 합은 15
3. 또 다른 방법 — 정렬 활용
배열을 오름차순으로 정렬한 뒤, 각 배열의 마지막 원소(즉, 최댓값)를 더하는 방법도 있습니다. 정렬에 O(n log n)의 시간이 소요되므로 최댓값만 찾는 방법보다는 다소 느리지만, 코드가 간결하다는 장점이 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int findMaxPairSum(int arr1[], int n1, int arr2[], int n2) {
sort(arr1, arr1 + n1);
sort(arr2, arr2 + n2);
return (arr1[n1 - 1] + arr2[n2 - 1]);
}
int main() {
int arr1[] = { 3, 7, 5 };
int arr2[] = { 8, 2, 4 };
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int n2 = sizeof(arr2) / sizeof(arr2[0]);
cout<<"두 배열에서 최대 합을 가지는 쌍의 합은 "<<findMaxPairSum(arr1, n1, arr2, n2);
return 0;
}
출력 결과
두 배열에서 최대 합을 가지는 쌍의 합은 15
정리
세 가지 방법을 비교하면 다음과 같습니다.
- 중첩 반복문: O(n1 × n2) — 모든 쌍을 탐색하므로 비효율적
- 최댓값 탐색: O(n1 + n2) — 가장 효율적이며 권장되는 방법
- 정렬 활용: O(n log n) — 코드는 간결하지만 정렬 비용 발생
원소가 모두 양수라는 조건이 주어진 경우에는 각 배열의 최댓값을 찾아 더하는 방식이 가장 효율적인 해결책입니다.