C++로 배열에서 a + b = c + d를 만족하는 네 개의 원소 찾기

문제 개요

정수로 이루어진 배열이 주어졌을 때, (a, b)와 (c, d)처럼 두 쌍을 이루는 서로 다른 네 개의 정수를 찾아 a + b = c + d 조건을 만족하도록 하는 것이 목표입니다. 가능한 답이 여러 개라면 그중 하나만 출력하면 됩니다.

예를 들어 배열이 A = [7, 5, 9, 3, 6, 4, 2]라고 한다면, (7, 3)과 (6, 4)와 같은 쌍을 찾을 수 있습니다. 실제로 7 + 3 = 10이고 6 + 4 = 10이므로 조건을 만족합니다.

접근 방법: 해싱(Hashing) 기법

이 문제는 해시 테이블(맵)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 두 원소의 합(sum)을 키(key)로, 그 합을 만드는 인덱스 쌍을 값(value)으로 저장하는 것입니다. 탐색 중에 이미 저장된 동일한 합을 발견하면, 그 순간 두 쌍이 조건을 만족하게 됩니다.

알고리즘 단계

• i를 0부터 n - 1까지 반복합니다.
• j를 i + 1부터 n - 1까지 반복합니다.
• arr[i] + arr[j]의 합을 계산합니다.
• 해시 테이블에 이미 동일한 합이 존재하면, 저장되어 있던 이전 쌍과 현재 쌍을 출력하고 종료합니다.
• 존재하지 않으면 현재 합과 인덱스 쌍을 해시 테이블에 추가합니다.

모든 쌍을 검사했음에도 조건을 만족하는 쌍을 찾지 못했다면, 그러한 쌍이 존재하지 않는다는 의미입니다.

C++ 구현 예제

#include<iostream>
#include<map>
using namespace std;

bool getTwoPairs(int arr[], int n) {
   map<int, pair<int, int> > hash_table;
   for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
         int sum = arr[i] + arr[j];
         if (hash_table.find(sum) == hash_table.end())
            hash_table[sum] = make_pair(i, j);
         else {
            pair<int, int> pp = hash_table[sum];
            cout << "(" << arr[pp.first] << " + " << arr[pp.second] << ") = (" << arr[i] << " + " << arr[j] << ")";
            return true;
         }
      }
   }
   cout << "No pairs found";
   return false;
}

int main() {
   int arr[] = {7, 5, 9, 3, 6, 4, 2};
   int n = sizeof arr / sizeof arr[0];
   cout << "The pairs are: ";
   getTwoPairs(arr, n);
}

실행 결과

The pairs are: (7 + 4) = (5 + 6)

출력 결과를 보면 7 + 4 = 11이고 5 + 6 = 11이므로, 두 쌍의 합이 서로 같다는 조건을 정확히 만족함을 확인할 수 있습니다.

복잡도 분석

배열에서 만들 수 있는 모든 쌍을 한 번씩 확인하므로 시간 복잡도는 O(n²)입니다. 또한 최악의 경우 모든 쌍의 합을 해시 테이블에 저장해야 하므로 공간 복잡도 역시 O(n²)입니다. 단순한 브루트 포스 방식(네 개의 중첩 반복문 사용, O(n⁴))보다 훨씬 효율적이라는 점이 이 방법의 가장 큰 장점입니다.