C++로 정렬되지 않은 배열에서 합이 같은 모든 쌍 찾아 출력하기

문제 개요

이 문제에서는 정렬되지 않은 배열(unsorted array)이 주어지며, 배열 내에 존재하는 원소들 중 합(sum)이 서로 동일한 모든 쌍(pair)을 찾아 출력해야 합니다.

예제를 통해 문제를 좀 더 구체적으로 살펴보겠습니다.

입력: array = [12, 13, 20, 5]
출력: [12, 13]과 [20, 5]의 합은 25로 동일합니다.

접근 방법

이 문제를 해결하려면 배열의 모든 원소 조합에 대해 쌍을 만들고, 각 쌍의 합을 계산한 뒤 합이 같은 쌍들을 그룹으로 묶어야 합니다. 또한 중복된 쌍이 여러 번 출력되는 것을 방지하기 위해 맵(map) 자료구조를 활용합니다.

이를 위해 두 개의 맵을 사용할 수 있습니다.

• 맵1 → key = 쌍(pair), value = 해당 쌍의 합
• 맵2 → key = 합(sum), value = 그 합을 가지는 쌍들의 벡터(vector of pair)

맵2를 기준으로 순회하면서, 동일한 합 값을 가지는 쌍이 둘 이상인 경우 해당 쌍들을 모두 출력하면 됩니다.

예제 코드

위 로직을 구현한 C++ 프로그램은 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;
void findEqualSumPairs(int A[], int n){
    map<int, vector<pair<int, int> > >map1;
    for (int i = 0; i < n - 1; i++) {
       for (int j = i + 1; j < n; j++) {
          pair<int, int> p = make_pair(A[i], A[j]);
          map1[A[i] + A[j]].push_back(p);
       }
   }
   for (auto value = map1.begin(); value != map1.end(); value++) {
      if (value->second.size() > 1) {
         for (int i = 0; i < value->second.size(); i++) {
            cout<<"[ "<<value->second[i].first<<", "<<value->second[i].second<<"] ";
         }
         cout<<"have sum : "<<value->first<<endl;
      }
   }
}
int main() {
    int A[] = { 6, 4, 12, 10, 22,11, 8, 2 };
    int n = sizeof(A) / sizeof(A[0]);
    cout<<"Pairs with same sum are : \n";
    findEqualSumPairs(A, n);
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같이 합이 같은 쌍들이 출력됩니다.

[ 6, 4] [ 8, 2] have sum : 10
[ 4, 8] [ 10, 2] have sum : 12
[ 6, 8] [ 4, 10] [ 12, 2] have sum : 14
[ 6, 10] [ 4, 12] have sum : 16
[ 6, 12] [ 10, 8] have sum : 18

정리

이 알고리즘은 배열의 모든 쌍을 한 번씩 확인하므로 시간 복잡도는 O(n²)입니다. 맵을 사용해 각 합별로 쌍을 그룹화하기 때문에 중복 없이 깔끔하게 결과를 출력할 수 있으며, 해시맵(unordered_map)을 사용하면 평균적으로 더 빠른 성능을 기대할 수 있습니다.