C++에서 주어진 합을 만족하는 모든 쌍 출력하기

이 문제에서는 정수 배열과 하나의 정수(sum)가 주어지며, 두 원소의 합이 주어진 값과 일치하는 모든 정수 쌍을 찾아 출력해야 합니다.

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

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

출력 − (1, 3), (6, -2)

즉, 배열에서 서로 다른 두 원소를 골라 그 합이 4가 되는 모든 조합을 찾으면 됩니다.

방법 1: 이중 반복문(브루트 포스)

가장 단순한 해결 방법은 배열의 모든 원소 쌍을 하나씩 검사하는 것입니다. 바깥쪽 반복문으로 각 원소를 순회하고, 안쪽 반복문으로 해당 원소 이후의 원소들 중 합이 sum이 되는 값을 찾는 방식입니다.

예제 코드

#include <iostream>
using namespace std;
int printPairsWithSum(int arr[], int n, int sum){
    int count = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (arr[i] + arr[j] == sum)
                cout<<"[ "<<arr[i]<<", "<<arr[j]<<" ]\n";
}
int main(){
    int arr[] = {1, 6, -2, 3};
    int n = 4;
    int sum = 4;
    cout<<"Pairs with Sum "<<sum<<" are :\n";
    printPairsWithSum(arr, n, sum);
    return 0;
}

실행 결과

Pairs with Sum 4 are :
[ 1, 3 ]
[ 6, -2 ]

이 방법은 이해하기 쉽다는 장점이 있지만, 시간 복잡도가 O(n²)이므로 배열의 크기가 커지면 비효율적입니다. 더 나은 성능을 원한다면 해싱(hash) 기법을 활용할 수 있습니다.

방법 2: 해시 테이블 활용

해시 테이블(unordered_map)을 사용하면 시간 복잡도를 O(n)까지 줄일 수 있습니다. 동작 방식은 다음과 같습니다.

배열을 순회하면서 각 원소에 대해 rem = sum − 현재 원소를 계산합니다. 만약 해시 테이블에 rem이 이미 존재한다면, 현재 원소와 rem의 합이 sum이 되는 것이므로 해당 쌍을 출력합니다. 이때 해시 테이블에는 각 값의 등장 횟수를 함께 저장하므로, 중복된 값이 여러 번 나타나는 경우에도 올바르게 처리할 수 있습니다. 마지막으로 현재 원소를 해시 테이블에 추가(카운트 증가)하고 다음 원소로 넘어갑니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
void printPairsWithSum(int arr[], int n, int sum){
    unordered_map<int, int> pair;
    for (int i = 0; i < n; i++) {
        int rem = sum - arr[i];
        if (pair.find(rem) != pair.end()) {
            int count = pair[rem];
            for (int j = 0; j < count; j++)
                cout<<"["<<rem<<", "<<arr[i]<<" ]\n";
        }
        pair[arr[i]]++;
    }
}
int main(){
    int arr[] = {1, 6, -2, 3};
    int n = 4;
    int sum = 4;
    cout<<"The pair with sum is \n";
    printPairsWithSum(arr, n, sum);
    return 0;
}

실행 결과

Pairs with Sum 4 are :
[ 1, 3 ]
[ 6, -2 ]

정리

두 방법 모두 동일한 결과를 출력하지만, 이중 반복문을 사용하는 첫 번째 방법은 구현이 간단한 대신 O(n²)의 시간이 걸리고, 해시 테이블을 사용하는 두 번째 방법은 평균적으로 O(n)의 시간 복잡도로 훨씬 효율적입니다. 따라서 입력 크기가 큰 경우에는 해싱 기반 접근 방식을 사용하는 것이 좋습니다.