C++로 두 배열의 교집합 구하기

문제 소개

두 개의 배열이 주어졌을 때, 두 배열의 교집합(intersection)을 구하는 문제입니다.

예를 들어 입력이 [1,5,3,6,9]와 [2,8,9,6,7]이라면, 두 배열에 공통으로 존재하는 원소는 9와 6이므로 출력은 [9,6]이 됩니다.

해결 접근 방법

이 문제는 해시 맵(unordered_map)을 활용하면 효율적으로 해결할 수 있습니다. 각 배열의 원소 빈도를 기록한 뒤, 양쪽 모두에 존재하는 원소만 결과에 담는 방식입니다.

알고리즘은 다음과 같은 단계로 진행됩니다.

• 두 개의 맵 mp1, mp2를 정의합니다.
• 결과를 저장할 배열 res를 정의합니다.
• nums1의 각 원소 x에 대해 mp1[x]의 값을 1씩 증가시킵니다.
• nums2의 각 원소 x에 대해 mp2[x]의 값을 1씩 증가시킵니다.
• mp1의 각 키-값 쌍 x에 대해 다음을 수행합니다.
  • cnt를 0으로 초기화합니다.
  • cnt를 x의 값(빈도)과 mp2[x의 키] 중 최솟값으로 설정합니다.
  • cnt가 0보다 크다면, 해당 키를 res의 끝에 추가합니다.
• res를 반환합니다.

여기서 최솟값을 사용하는 이유는, 한 배열에서 여러 번 등장한 원소라도 다른 배열에 없다면 교집합에서 제외되어야 하기 때문입니다.

구현 예제

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2){
        unordered_map<int, int> mp1, mp2;
        vector<int> res;
        for (auto x : nums1)
            mp1[x]++;
        for (auto x : nums2)
            mp2[x]++;
        for (auto x : mp1) {
            int cnt = 0;
            cnt = min(x.second, mp2[x.first]);
            if (cnt > 0)
                res.push_back(x.first);
        }
        return res;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,5,3,6,9}, v1 = {2,8,9,6,7};
    print_vector(ob.intersection(v, v1));
}

입력

{1,5,3,6,9},{2,8,9,6,7}

출력

[9, 6]

복잡도 분석

이 알고리즘의 시간 복잡도는 O(n + m)입니다. 여기서 n과 m은 각각 두 배열의 길이를 의미합니다. 각 배열을 한 번씩 순회하며 맵을 채우고, 맵의 크기에 비례하는 순회 한 번으로 결과를 만들기 때문입니다. 공간 복잡도 역시 맵에 원소를 저장하므로 O(n + m)입니다.