C++로 구하는 두 배열에서 합이 K가 되는 고유한 쌍의 개수

두 개의 정수 배열 Arr1[]과 Arr2[], 그리고 목표 합 K가 주어졌을 때, 두 배열의 원소로 구성된 쌍 (Arr1[i], Arr2[j]) 가운데 Arr1[i] + Arr2[j] == K를 만족하는 고유한 쌍의 개수를 구하는 것이 목표입니다.

가장 직관적인 방법은 두 개의 반복문으로 i와 j를 순회하면서 모든 조합을 확인하는 것입니다. 합이 K가 되고, 아직 unordered_map<int, int>에 등록되지 않은 쌍이라면 맵에 추가하고 카운트를 1 증가시킵니다. 이렇게 하면 같은 값을 가진 쌍이 여러 번 발견되더라도 한 번만 계산됩니다.

예제를 통해 자세히 살펴보겠습니다.

예제 1

입력

Arr1[] = { 1, 3, 2, 4, 3, 2 };  Arr2[] = { 0, 2, 1, 2, 3 };  K = 4

출력

합이 K인 쌍의 개수 : 4

설명

(1, 3) → 1 + 3 = 4
(3, 1) → 3 + 1 = 4
(2, 2) → 2 + 2 = 4
(4, 0) → 4 + 0 = 4
중복되는 쌍은 제외되며, 고유한 쌍은 총 4개입니다.

예제 2

입력

Arr1[] = { 0, 2, 1, 2, 3 };  Arr2[] = { 1, 1, 1, 1, 1 };  K = 3

출력

합이 K인 쌍의 개수 : 1

설명

(2, 1) → 2 + 1 = 3
조건을 만족하는 유일한 고유 쌍이므로 답은 1입니다.

접근 방식

두 배열 Arr1[], Arr2[]와 목표 합 K를 입력으로 받습니다.
len1과 len2는 각각 두 배열의 길이를 나타냅니다.
pairsumisK(int arr1[], int arr2[], int k, int l1, int l2) 함수는 합이 k가 되는 고유한 쌍의 개수를 반환합니다.
쌍의 개수를 세기 위한 변수 count를 0으로 초기화합니다.
이미 발견한 고유한 쌍을 저장하기 위해 unordered_map umap을 사용합니다.
두 개의 for 반복문으로 두 배열의 모든 조합을 순회합니다.
arr1[]은 i = 0부터 i < len1까지, arr2[]는 j = 0부터 j < len2까지 탐색합니다.
arr1[i] + arr2[j] == k를 만족하면, umap.find(...) == umap.end() 조건으로 해당 쌍이 이미 등록되어 있는지 확인합니다.
등록되어 있지 않다면 쌍을 umap에 삽입하고 count를 증가시킵니다.
모든 반복이 끝나면 count에는 조건을 만족하는 고유한 쌍의 총 개수가 저장됩니다.
count를 결과로 반환합니다.

이 방법의 시간 복잡도는 O(len1 × len2)이며, unordered_map 덕분에 각 쌍의 중복 여부를 평균 O(1) 시간에 확인할 수 있습니다.

C++ 구현 예제

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

// 합이 k가 되는 두 배열 원소의 고유한 쌍 개수를 반환
int pairsumisK(int arr1[], int arr2[], int k, int l1, int l2){
    int count = 0;
    unordered_map<int, int> umap; // 이미 찾은 고유한 쌍 저장
    for (int i = 0; i < l1; i++){
        for (int j = 0; j < l2; j++){
            int sum = arr1[i] + arr2[j];
            if (sum == k){ // 합이 k인 경우만 처리
                // 아직 등록되지 않은 고유한 쌍만 추가
                if (umap.find(arr1[i]) == umap.end()){
                    umap.insert(make_pair(arr1[i], arr2[j]));
                    count++;
                }
            }
        }
    }
    return count;
}
int main(){
    int Arr1[] = { 1, 2, 3, 0, 2, 4 };
    int Arr2[] = { 3, 2, 5, 2 };
    int len1 = sizeof(Arr1) / sizeof(Arr1[0]);
    int len2 = sizeof(Arr2) / sizeof(Arr2[0]);
    int K = 5; // 목표 합
    cout << endl << "합이 K인 쌍의 개수 : " << pairsumisK(Arr1, Arr2, K, len1, len2);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

합이 K인 쌍의 개수 : 3

배열 Arr1 = { 1, 2, 3, 0, 2, 4 }, Arr2 = { 3, 2, 5, 2 }, K = 5일 때 조건을 만족하는 고유한 쌍은 (2, 3), (3, 2), (0, 5)로 총 3개입니다. 참고로 원본 예제 코드에는 count를 증가시키는 부분이 누락되어 있어 항상 0이 출력되는 오류가 있었으며, 위 코드에는 이를 바르게 수정했습니다.