C++로 배열에서 최솟값과 두 번째 최솟값의 최대 합 구하기

이 문제에서는 배열 arr[]가 주어지며, 우리의 목표는 배열에서 가장 작은 값과 두 번째로 작은 값의 합이 가장 커지는 경우를 찾아 그 최대 합을 구하는 프로그램을 작성하는 것입니다.

문제 설명

배열의 모든 부분 배열(subarray)에 대해 각 부분 배열 내에서 가장 작은 원소와 두 번째로 작은 원소의 합을 계산하고, 이러한 합들 중 최대값을 반환해야 합니다.

예시

예제를 통해 문제를 자세히 이해해 보겠습니다.

입력

arr[] = {3, 5, 4, 2, 9, 1, 6}

출력

11

설명

가능한 모든 부분 배열 중,
{2, 9}에서 최솟값들의 합이 가장 큽니다.
합 = 2 + 9 = 11

해결 접근 방식

가장 단순한 방법은 가능한 모든 부분 배열을 생성하는 것입니다. 각 부분 배열마다 최솟값과 두 번째 최솟값을 찾아 합을 구한 뒤, 그중 최대값을 반환하면 됩니다. 하지만 이 방법은 시간 복잡도가 O(n²) 이상으로 비효율적입니다.

더 효율적인 방법은 예시에서 얻을 수 있는 핵심 관찰에 기반합니다. 어떤 부분 배열의 최솟값과 두 번째 최솟값 사이에 위치한 원소는 반드시 두 번째 최솟값보다 크거나 같으므로, 이 두 원소를 포함하는 범위를 인접한 두 원소의 쌍까지 좁혀도 결과는 달라지지 않습니다. 따라서 정답은 배열에서 인접한 두 원소의 합 중 가장 큰 값과 같습니다.

알고리즘

초기화 −

maxSum = -1

1단계 −

i를 0부터 n-2까지 순회

1.1단계 −

만약 maxSum < (arr[i] + arr[i+1])이라면, maxSum = (arr[i] + arr[i+1])로 갱신

2단계 −

maxSum을 반환

이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.

예제 코드

풀이의 동작을 보여주는 C++ 프로그램입니다.

#include <iostream>
using namespace std;
int calcMaxSumPairs(int arr[], int n) {
    int maxSum = -1;
    for (int i = 0; i < (n - 1); i++)
        if (maxSum < (arr[i] + arr[i + 1]))
            maxSum = (arr[i] + arr[i + 1]);
    return maxSum;
}
int main() {
    int arr[] = {3, 4, 2, 9, 5, 6};
    int n = sizeof(arr) / sizeof(int);
    cout << "배열에서 최솟값과 두 번째 최솟값의 최대 합은 "
         << calcMaxSumPairs(arr, n);
    return 0;
}

출력

배열에서 최솟값과 두 번째 최솟값의 최대 합은 14