C++에서 합이 주어진 값 x와 같은 두 배열의 쌍 개수 구하기

문제 개요

양수로만 구성된 두 개의 배열과 하나의 값 x가 주어집니다. 찾아야 하는 것은 첫 번째 배열에서 원소 A를, 두 번째 배열에서 원소 B를 선택하여 A + B = x를 만족하는 쌍 (A, B)의 개수입니다.

예제로 이해하기

입력 − arr_1[] = {1, 2, 5, 3, 4}, arr_2[] = {7, 0, 1, 3}, x = 6

출력 − 합이 x와 같은 쌍의 개수: 2

설명 − 조건을 만족하는 쌍은 (5, 1)과 (3, 3)입니다.

입력 − arr_1[] = {1, 1, 1}, arr_2[] = {2, 2}, x = 3

출력 − 합이 x와 같은 쌍의 개수: 6

설명 − arr_1의 모든 원소(1)와 arr_2의 모든 원소(2)를 짝지으면 1 + 2 = 3이 되므로 총 3 × 2 = 6개의 쌍이 만들어집니다.

방법 1: 브루트 포스(완전 탐색)

가장 직관적인 방법은 이중 반복문을 사용하는 것입니다. 인덱스 i로 arr_1[]을, 인덱스 j로 arr_2[]를 순회하며 가능한 모든 조합을 확인하고, arr_1[i] + arr_2[j] == x를 만족할 때마다 카운트를 증가시킨 뒤 최종 카운트를 반환합니다.

• 양의 정수를 담은 배열 arr_1[], arr_2[]와 각각의 길이 size_arr_1, size_arr_2를 준비합니다.
• 함수 Pair_value_x(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int x)는 두 배열과 길이, 목표값 x를 받아 합이 x가 되는 쌍의 개수를 반환합니다.
• 카운트 변수를 0으로 초기화합니다.
• i = 0부터 i < size_arr_1까지, j = 0부터 j < size_arr_2까지 이중 반복문으로 두 배열을 순회합니다.
• 각 쌍 (arr_1[i], arr_2[j])에 대해 합이 x인지 검사하고, 참이면 카운트를 증가시킵니다.
• 카운트를 결과로 반환합니다.

이 방법의 시간 복잡도는 O(n × m)으로, 배열의 크기가 커질수록 비효율적입니다.

방법 2: unordered_set(해시셋)을 활용한 효율적인 접근

해시 기반 자료구조를 사용하면 성능을 크게 개선할 수 있습니다. 먼저 arr_1의 모든 원소를 unordered_set에 저장한 뒤, arr_2를 순회하면서 각 원소 arr_2[i]에 대해 x − arr_2[i]가 집합에 존재하는지만 확인하면 됩니다. 존재한다면 그 값과 짝을 이루는 원소가 arr_1에 있다는 의미이므로 카운트를 증가시킵니다.

• 동일하게 두 배열과 각각의 크기를 준비합니다.
• 함수 Pair_value_x(...)는 합이 x가 되는 쌍의 개수를 반환합니다.
• 카운트를 0으로 초기화합니다.
• arr_1의 고유한 원소를 저장할 unordered_set<int> 타입의 hash_map을 생성합니다.
• 반복문으로 arr_1의 모든 원소를 hash_map에 삽입합니다.
• 반복문으로 arr_2[]를 순회합니다.
• 각 arr_2[j]에 대해 hash_map.find(x - arr_2[j]) != hash_map.end() 조건으로 x − arr_2[j]가 집합에 있는지 확인하고, 존재하면 카운트를 증가시킵니다.
• 최종 카운트가 곧 합이 x가 되는 쌍의 개수입니다.
• 카운트를 결과로 반환합니다.

이 방법은 평균 O(n + m)의 시간 복잡도를 가지므로 브루트 포스보다 훨씬 빠르며, 대신 O(n)의 추가 메모리가 필요합니다.

예제 코드 (브루트 포스)

#include <bits/stdc++.h>
using namespace std;
int Pair_value_x(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int x){
    int count = 0;
    for (int i = 0; i < size_arr_1; i++){
        for (int j = 0; j < size_arr_2; j++){
            if ((arr_1[i] + arr_2[j]) == x){
                count++;
            }
        }
    }
    return count;
}
int main(){
    int arr_1[] = {1, 2, 3, 4};
    int arr_2[] = {2, 3, 4, 5};
    int size_arr_1 = sizeof(arr_1) / sizeof(arr_1[0]);
    int size_arr_2 = sizeof(arr_2) / sizeof(arr_2[0]);
    int x = 6;
    cout<<"합이 x와 같은 쌍의 개수: "<<Pair_value_x(arr_1, arr_2, size_arr_1 , size_arr_2, x);
    return 0;
}

출력

위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −

합이 x와 같은 쌍의 개수: 4

예제 코드 (unordered_set 활용)

#include <bits/stdc++.h>
using namespace std;
int Pair_value_x(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int x){
    int count = 0;
    unordered_set<int> hash_map;
    for (int i = 0; i < size_arr_1; i++){
        hash_map.insert(arr_1[i]);
    }
    for (int j = 0; j < size_arr_2; j++){
        if (hash_map.find(x - arr_2[j]) != hash_map.end()){
            count++;
        }
    }
    return count;
}
int main(){
    int arr_1[] = {1, 2, 3, 4};
    int arr_2[] = {2, 3, 4, 5};
    int size_arr_1 = sizeof(arr_1) / sizeof(arr_1[0]);
    int size_arr_2 = sizeof(arr_2) / sizeof(arr_2[0]);
    int x = 6;
    cout<<"합이 x와 같은 쌍의 개수: "<<Pair_value_x(arr_1, arr_2, size_arr_1 , size_arr_2, x);
    return 0;
}

출력

위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −

합이 x와 같은 쌍의 개수: 4

마무리

두 배열에서 합이 특정 값이 되는 쌍을 찾는 문제는 코딩 테스트에서 자주 등장하는 유형입니다. 데이터 크기가 작다면 단순한 이중 반복문으로 충분하지만, 입력이 커질수록 unordered_set을 활용한 해시 기반 접근이 시간 복잡도 면에서 훨씬 유리합니다. 상황에 맞는 방법을 선택해 적용해 보시기 바랍니다.