C++로 두 배열의 겹치는 원소 합 구하기

문제 개요

이 문제에서는 중복 없는 고유한 값들로 이루어진 두 배열 arr1[]과 arr2[]가 주어집니다. 우리의 목표는 두 배열에 공통으로 존재하는 원소들의 합(겹치는 합)을 구하는 것입니다.

공통 원소는 양쪽 배열에서 각각 한 번씩 등장하므로, 해당 값은 합계에 두 번 더해진다는 점에 유의해야 합니다.

예제로 문제 이해하기

입력:

arr1[] = {5, 4, 9, 2}, arr2[] = {6, 3, 9, 4}

출력:

26

설명:

두 배열에 모두 존재하는 원소는 9와 4입니다.
따라서 최종 합은 9 + 9 + 4 + 4 = 26이 됩니다.

해결 접근 방법

1. 브루트 포스(완전 탐색)

가장 단순한 방법은 한 배열(arr1[])을 순회하면서 각 원소마다 다른 배열(arr2[])에 같은 값이 존재하는지 확인하는 것입니다. 일치하는 원소를 발견하면 그 값을 합계에 더하고, 최종적으로 두 배를 반환합니다.

이 방식은 반복문을 중첩해서 사용해야 하므로 시간 복잡도는 O(N²)입니다. 입력 크기가 커지면 성능이 급격히 저하될 수 있습니다.

2. 해싱(Hashing) 활용

더 효율적인 방법은 해시 테이블을 사용하는 것입니다. 두 배열의 모든 원소를 해시 테이블에 저장하면서 각 원소의 빈도수를 함께 기록합니다. 이후 빈도수가 2인 원소, 즉 두 배열 모두에 등장하는 원소만 골라 합산한 뒤 그 합에 2를 곱하여 반환하면 됩니다.

해싱을 활용하면 평균적으로 시간 복잡도 O(N), 공간 복잡도 O(N)으로 문제를 해결할 수 있어 훨씬 효율적입니다.

C++ 구현 예제

다음 프로그램은 위에서 설명한 해싱 기반 해결책의 동작을 보여줍니다.

#include <bits/stdc++.h>
using namespace std;
int findCommonValSum(int A[], int B[], int n){
    unordered_map<int,int> hashTable;
    for(int i=0;i<n;i++){
        if(hashTable.find(A[i])==hashTable.end())
            hashTable.insert(make_pair(A[i],1));
        else
            hashTable[A[i]]++;

        if(hashTable.find(B[i])==hashTable.end())
            hashTable.insert(make_pair(B[i],1));
        else
            hashTable[B[i]]++;
    }
    int commSum = 0;
    for(auto itr = hashTable.begin(); itr!=hashTable.end(); itr++){
        if((itr->second)==2){
            commSum += (itr->first);
        }
    }
    return (commSum*2);
}
int main(){
    int A[] = { 5, 4, 9, 2 };
    int B[] = { 6, 3, 9, 4 };
    int n = sizeof(A) / sizeof(A[0]);
    cout<<"The sum of common values in the array are "<<findCommonValSum(A, B, n);
    return 0;
}

실행 결과

The sum of common values in the array are 26

프로그램은 두 배열의 공통 원소인 9와 4를 정확히 식별하고, 각 값을 두 번씩 더한 최종 합계 26을 출력합니다.

마무리

두 배열의 겹치는 합을 구하는 문제는 단순 완전 탐색으로도 해결할 수 있지만, 해시 맵을 활용하면 선형 시간 안에 효율적으로 처리할 수 있습니다. 빈도수 계산이라는 해싱의 기본 원리를 응용한 대표적인 예제이므로, 유사한 교집합·빈도 관련 문제를 풀 때 유용하게 참고할 수 있습니다.