C++ 배열에서 a + b + c = d를 만족하는 가장 큰 d 찾기

문제 정의

정수들로 이루어진 집합이 주어졌을 때, 같은 집합 안의 세 수 a, b, c의 합으로 표현되는 수 d, 즉 d = a + b + c를 만족하는 값 중 가장 큰 것을 찾아야 합니다. 이때 a, b, c, d는 모두 집합에 반드시 존재해야 하며, 집합의 크기는 최소 1개부터 최대 1000개까지 가능하고 각 원소는 유한한 수입니다.

예를 들어 집합이 {2, 3, 5, 7, 12}라고 한다면, 12는 2 + 3 + 7로 나타낼 수 있으므로 가장 큰 d는 12가 됩니다.

해결 접근 방식: 해싱(Hashing)

이 문제는 해싱 기법을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

배열 내 모든 두 수의 합(a + b)을 해시 테이블에 저장합니다. 이때 해당 합을 만드는 두 원소의 인덱스도 함께 기록해 둡니다.
모든 두 수의 쌍(c, d)을 순회하면서, 두 수의 차(d − c)가 해시 테이블에 존재하는지 확인합니다.
존재한다면 d = a + b + c가 성립하는 것이므로, 네 인덱스가 서로 겹치지 않는지 검사한 뒤 d의 최댓값을 갱신합니다.

인덱스 겹침 검사가 중요한 이유는, 동일한 원소를 두 번 사용하거나 같은 쌍을 중복해서 계산하는 오류를 방지하기 위해서입니다.

C++ 구현 예시

#include<iostream>
#include<unordered_map>
#include<climits>
using namespace std;

// d = a + b + c를 만족하는 가장 큰 d를 찾는 함수
int findElementsInSet(int arr[], int n) {
    // 모든 두 수의 합(a + b)을 해시 테이블에 저장 (인덱스 쌍과 함께)
    unordered_map<int, pair<int, int> > table;
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
            table[arr[i] + arr[j]] = { i, j };

    int d = INT_MIN;
    // 모든 쌍(c, d)에 대해 (d - c)가 해시 테이블에 있는지 확인
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            int abs_diff = abs(arr[i] - arr[j]);
            if (table.find(abs_diff) != table.end()) {
                pair<int, int> p = table[abs_diff];
                // 네 인덱스가 모두 서로 달라야 함 (같은 원소 재사용 방지)
                if (p.first != i && p.first != j && p.second != i && p.second != j)
                    d = max(d, max(arr[i], arr[j]));
            }
        }
    }
    return d;
}

int main() {
    int arr[] = { 2, 3, 5, 7, 12 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int res = findElementsInSet(arr, n);
    if (res == INT_MIN)
        cout << "Cannot find the value of d";
    else
        cout << "Max value of d is " << res;
}

출력 결과

Max value of d is 12

복잡도 분석

두 수의 합을 모두 해시 테이블에 저장하는 데 O(n²)의 시간이 걸리고, 모든 쌍을 탐색하는 과정 역시 O(n²)이므로 전체 시간 복잡도는 O(n²)입니다. 공간 복잡도는 해시 테이블에 최대 n(n−1)/2개의 합이 저장될 수 있으므로 역시 O(n²)입니다. 완전 탐색으로 네 수를 일일이 조합하는 O(n⁴) 방식보다 상당히 효율적이라는 점이 이 접근법의 가장 큰 장점입니다.