이 튜토리얼에서는 배열에서 가장 작은 요소와 두 번째로 작은 요소의 최대 합을 구하는 프로그램을 다룹니다.
정수로 이루어진 배열이 주어졌을 때, 가능한 모든 부분 배열(subarray)에 대해 각각 '가장 작은 값 + 두 번째로 작은 값'을 계산하고, 그중 최댓값을 찾는 것이 목표입니다.
접근 방법
이 문제의 핵심 아이디어는 다음과 같습니다. 임의의 부분 배열에서 가장 작은 값과 두 번째로 작은 값의 합은, 해당 부분 배열 내에 존재하는 인접한 두 요소의 합보다 클 수 없습니다. 따라서 전체 배열을 한 번만 순회하면서 인접한 두 요소의 합 중 최댓값을 구하면 곧바로 정답을 얻을 수 있습니다.
예를 들어 배열 {4, 3, 1, 5, 6}의 인접 쌍의 합은 각각 7(4+3), 4(3+1), 6(1+5), 11(5+6)이며, 이중 최댓값인 11이 정답이 됩니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
// 가장 작은 값과 두 번째로 작은 값의
// 최대 합을 반환하는 함수
int pairWithMaxSum(int arr[], int N) {
// 요소가 2개 미만이면 쌍을 만들 수 없음
if (N < 2)
return -1;
// 첫 번째 인접 쌍의 합으로 결과 초기화
int res = arr[0] + arr[1];
// 모든 인접 쌍의 합을 비교하며 최댓값 갱신
for (int i = 1; i < N - 1; i++)
res = max(res, arr[i] + arr[i + 1]);
return res;
}
int main() {
int arr[] = {4, 3, 1, 5, 6};
int N = sizeof(arr) / sizeof(int);
cout << pairWithMaxSum(arr, N) << endl;
return 0;
}실행 결과
11
코드 설명
함수 pairWithMaxSum은 먼저 배열의 크기가 2보다 작으면 쌍을 만들 수 없으므로 -1을 반환합니다. 이후 결과 변수 res를 첫 번째 인접 쌍의 합으로 초기화하고, 반복문을 통해 나머지 모든 인접 쌍의 합을 비교하며 더 큰 값으로 갱신합니다. 마지막으로 갱신된 최댓값을 반환합니다.
복잡도 분석
배열을 한 번만 순회하므로 시간 복잡도는 O(N)이며, 추가적인 저장 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다. 덕분에 배열의 크기가 매우 커도 효율적으로 동작합니다.