문제 소개
이 문제에서는 정렬되지 않은 N개의 요소로 이루어진 배열 arr[]이 주어집니다. 우리의 목표는 배열에서 합이 가장 큰 두 요소의 쌍(pair)을 찾는 것입니다.
즉, 배열 안에서 두 개의 요소를 골랐을 때 그 합이 최대가 되는 조합을 구하면 됩니다.
예시를 통해 문제를 자세히 살펴보겠습니다.
입력 : arr[] = {7, 3, 9, 12, 1}
출력 : 21설명 −
합이 가장 큰 쌍은 (9, 12)이며, 그 합은 21입니다.
해결 접근 방법
이 문제의 가장 효율적인 해결책은 배열에서 최댓값(max)과 두 번째로 큰 값(secondMax)을 찾아 이 둘을 더하는 것입니다.
구체적인 진행 과정은 다음과 같습니다.
먼저 배열의 첫 번째 요소와 두 번째 요소를 서로 비교하여, 더 큰 값을 max로, 작은 값을 secondMax로 초기화합니다.
그다음 인덱스 2부터 (n-1)까지 배열을 순회하며 각 요소를 max 및 secondMax 값과 비교합니다.
- arr[i]가 max보다 크다면, 기존의 max 값을 secondMax에 저장하고 arr[i]를 새로운 max로 설정합니다.
- arr[i]가 secondMax보다 크고(단, max와 같지 않은 경우), secondMax를 arr[i]로 갱신합니다.
순회가 모두 끝나면 max + secondMax를 반환하면 됩니다. 이 방법은 배열을 딱 한 번만 순회하므로 시간 복잡도가 O(n)으로 매우 효율적이며, 배열 전체를 정렬하는 O(n log n) 방식보다 성능 면에서 유리합니다.
예제 코드
아래 프로그램은 위에서 설명한 솔루션의 실제 동작을 보여줍니다.
#include<iostream>
using namespace std;
int findPairLargestSum(int arr[], int n){
int max, secondMax;
if (arr[0] > arr[1]){
max = arr[0];
secondMax = arr[1];
}
else{
max = arr[1];
secondMax = arr[0];
}
for (int i = 2; i<n; i++){
if (arr[i] > max){
secondMax = max;
max = arr[i];
}
else if (arr[i] > secondMax && arr[i] != max)
secondMax = arr[i];
}
return (max + secondMax);
}
int main(){
int arr[] = {12, 34, 10, 6, 40};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"최대 합을 가진 쌍의 요소 합계는 "<<findPairLargestSum(arr, n);
return 0;
}출력 결과
최대 합을 가진 쌍의 요소 합계는 74
위 예제에서 배열 {12, 34, 10, 6, 40} 중 가장 큰 두 값은 40과 34이며, 이 둘의 합인 74가 출력됩니다.
참고 사항
이 알고리즘이 올바르게 동작하려면 배열에 최소 두 개 이상의 요소가 있어야 합니다. 따라서 실제 코드에 적용할 때는 n이 2 미만인 경우에 대한 예외 처리를 추가하는 것이 좋습니다. 또한 중복된 최댓값이 여러 개 존재하는 경우에도 코드의 조건문(arr[i] != max)이 이를 적절히 처리하여 정확한 결과를 보장합니다.