C++로 배열에서 합이 이미 배열 안에 존재하는 쌍 찾기

문제 개요

이 문제에서는 N개의 정수로 구성된 배열 arr[]가 주어집니다. 우리의 과제는 배열에서 두 원소의 합이 그 자체로 배열 안에 이미 존재하는 모든 쌍(pair)을 찾는 것입니다.

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

입력

arr[] = {1, 2, 4, 6, 7}

출력

(1, 6), (2, 4)

설명

쌍 (1, 6)의 경우, 두 값의 합은 7이며 이 값은 배열에 존재합니다.

쌍 (2, 4)의 경우, 두 값의 합은 6이며 이 값 역시 배열에 존재합니다.

해결 방법 1: 브루트 포스(Brute Force)

가장 단순한 해결 방법은 배열의 원소들로 만들 수 있는 모든 쌍을 일일이 확인하는 것입니다. 각 쌍의 합을 계산한 뒤, 그 합이 배열 안에 존재하는지 검색하고, 존재하면 해당 쌍을 출력합니다.

또한 조건을 만족하는 쌍의 개수를 세는 카운터를 두고, 개수가 0이라면 "쌍을 찾을 수 없다"는 메시지를 출력하도록 합니다.

이 해결 방법의 동작을 보여주는 프로그램입니다.

예제 코드

#include <iostream>
using namespace std;

void findSumPairsArr(int arr[], int n){
    int pairCount = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = 0; k < n; k++) {
                if (arr[i] + arr[j] == arr[k]) {
                    cout<<"( "<<arr[i]<<", "<<arr[j]<<" ), sum = "<<(arr[i] + arr[j])<<"\n";
                    pairCount++;
                }
            }
        }
    }
    if (!pairCount)
        cout<<"No Such Pairs found !";
}

int main() {
    int arr[] = { 1, 2, 4, 6, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"Pairs in array whose sum already exists in array : \n";
    findSumPairsArr(arr, n);
    return 0;
}

실행 결과

배열에서 합이 이미 존재하는 쌍 −

( 1, 6 ), sum = 7
( 2, 4 ), sum = 6

이 방식은 세 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n³)입니다. 배열의 크기가 커지면 성능이 급격히 저하된다는 단점이 있습니다.

해결 방법 2: 해시 테이블 활용

더 효율적인 접근 방식은 해시 테이블을 이용하는 것입니다. 먼저 배열의 모든 원소를 해시 테이블에 저장한 후, 각 쌍의 합을 계산하여 그 값이 해시 테이블에 존재하는지만 확인하면 됩니다. 이렇게 하면 배열 전체를 다시 검색할 필요가 없어 탐색 속도가 크게 향상됩니다.

C++에서는 STL의 unordered_set을 사용해 해시 테이블을 손쉽게 구현할 수 있습니다. 마찬가지로 조건을 만족하는 쌍이 하나도 없으면 "No Such Pairs found !"를 출력합니다.

이 해결 방법의 동작을 보여주는 프로그램입니다.

예제 코드

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

void findSumPairsArr(int arr[], int n) {
    unordered_set<int> HT;
    for (int i = 0; i < n; i++)
        HT.insert(arr[i]);

    int pairCount = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (HT.find(arr[i] + arr[j]) != HT.end()) {
                cout<<"( "<<arr[i]<<", "<<arr[j]<<" ), sum = "<<(arr[i] + arr[j])<<"\n";
                pairCount++;
            }
        }
    }
    if (!pairCount)
        cout<<"No Such Pairs found !";
}

int main() {
    int arr[] = {1, 2, 4, 6, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"Pairs in array whose sum already exists in array : \n";
    findSumPairsArr(arr, n);
    return 0;
}

실행 결과

배열에서 합이 이미 존재하는 쌍 −

( 1, 6 ), sum = 7
( 2, 4 ), sum = 6

해시 테이블을 사용하면 원소 존재 여부를 평균 O(1) 시간에 확인할 수 있으므로, 전체 시간 복잡도가 O(n²)으로 개선됩니다. 공간 복잡도는 해시 테이블 저장을 위해 O(n)이 추가로 필요합니다.