C++로 배열에서 최대 삼중항(Triplet) 합 구하기

이 문제에서는 하나의 배열이 주어지며, 우리의 과제는 배열에서 최대 삼중항 합(maximum triplet sum)을 찾는 프로그램을 작성하는 것입니다. 즉, 세 개의 원소를 골랐을 때 그 합이 가장 커지는 조합을 찾아야 합니다.

문제 이해하기

예시를 통해 문제를 살펴보겠습니다.

입력 − array = {4, 6, 1, 2}

출력 − 12

설명 −

배열의 모든 삼중항 :
(4, 6, 1) = 4+6+1 = 11
(4, 6, 2) = 4+6+2 = 12
(4, 1, 2) = 4+1+2 = 7
(6, 1, 2) = 6+1+2 = 9
따라서 최대 삼중항 합은 12입니다.

방법 1: 완전 탐색(Brute Force)

가장 단순한 접근 방식은 위 예시에서 확인한 것처럼, 가능한 모든 삼중항 조합의 합을 계산한 뒤 그중 최댓값을 찾는 것입니다. 세 개의 중첩 반복문을 실행하여 모든 삼중항의 합을 구하고, 현재까지의 최대합(maxSum)보다 크면 값을 갱신하는 방식입니다.

하지만 이 방법은 배열의 길이가 길어질수록 삼중항의 개수가 급격히 늘어나므로 비효율적입니다. 시간 복잡도는 O(n³)으로, 입력 크기가 커지면 성능이 크게 저하됩니다.

예제 코드

#include <iostream>
using namespace std;

int maxSum(int arr[], int n){
    int maxSum = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            for (int k = j + 1; k < n; k++)
                if (maxSum < arr[i] + arr[j] + arr[k])
                    maxSum = arr[i] + arr[j] + arr[k];
    return maxSum;
}

int main(){
    int arr[] = { 3, 5, 7, 1, 9, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "배열의 최대 삼중항 합은 " << maxSum(arr, n);
    return 0;
}

출력

배열의 최대 삼중항 합은 21

방법 2: 정렬 활용 (효율적 접근)

훨씬 효율적인 방법은 배열을 먼저 오름차순으로 정렬한 뒤, 마지막 세 개의 원소(가장 큰 세 값)의 합을 구하는 것입니다. 배열이 정렬되어 있다면 최대 삼중항은 반드시 가장 큰 세 원소로 구성되기 때문입니다. 이 방법의 시간 복잡도는 정렬에 의해 O(n log n)으로 완전 탐색보다 월등히 빠릅니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

int maxSum(int arr[], int n) {
    sort(arr, arr + n);
    return arr[n - 1] + arr[n - 2] + arr[n - 3];
}

int main() {
    int arr[] = { 3, 5, 9, 1, 2, 8, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "배열의 최대 삼중항 합은 " << maxSum(arr, n);
    return 0;
}

출력

배열의 최대 삼중항 합은 24

참고: 음수가 포함된 경우와 추가 최적화

완전 탐색 코드에서 maxSum을 0으로 초기화하면 배열 전체가 음수일 때 잘못된 결과가 나올 수 있습니다. 이 경우 첫 번째 삼중항의 합 또는 INT_MIN으로 초기화하는 것이 안전합니다.

또한 정렬조차 하지 않고 O(n) 한 번의 순회로 해결할 수도 있습니다. 배열을 한 번만 훑으면서 최댓값, 두 번째 최댓값, 세 번째 최댓값 세 변수를 유지하면 되는데, 이는 정렬 기반 방법보다도 빠른 최적의 해법입니다.