LeetCode 350번 Intersection of Two Arrays II
LeetCode 350번 Intersection of Two Arrays II

목차

 

문제 문제 링크

두 개의 정수 배열 `nums1`과 `nums2`가 주어질 때, 두 배열의 교집합을 반환하세요. 결과에 나타나는 각 원소의 횟수는 두 배열에서 나타나는 횟수의 최소값과 같아야 합니다. 결과는 임의의 순서로 반환할 수 있습니다.

입력

두 개의 정수 배열 `nums1`과 `nums2`가 주어집니다.

예제 입력 1

nums1 = [1,2,2,1], nums2 = [2,2]

출력

두 배열의 교집합을 반환합니다. 각 원소의 등장 횟수는 두 배열에서의 최소 등장 횟수와 같아야 합니다.

예제 출력 1

[2,2]

풀이

문제 해결 방법

이 문제는 두 배열의 교집합을 찾는 문제입니다. 주요 해결 방법은 다음과 같습니다:

  1. 해시 테이블을 이용한 해결 방법:
    • 첫 번째 배열의 각 원소와 등장 횟수를 해시 테이블에 저장
    • 두 번째 배열을 순회하며 해시 테이블에 있는 원소를 결과에 추가
  2. 정렬 후 이진 탐색을 이용한 해결 방법:
    • 두 배열을 정렬
    • 첫 번째 배열의 각 원소에 대해 두 번째 배열에서 이진 탐색으로 찾기
  3. 정렬 후 투 포인터를 이용한 해결 방법:
    • 두 배열을 정렬
    • 두 포인터를 사용하여 공통 원소 찾기

해시 테이블 방법의 시간 복잡도는 O(N+M)이고, 공간 복잡도는 O(min(N,M))입니다.

코드

class Solution {
public:
    vector intersect(vector& nums1, vector& nums2) {
        // nums1이 더 작은 배열이 되도록 스왑
        if (nums1.size() > nums2.size()) {
            return intersect(nums2, nums1);
        }
        
        // nums1의 각 원소와 등장 횟수를 해시 테이블에 저장
        unordered_map<int, int> count;
        for (int num : nums1) {
            count[num]++;
        }
        
        vector result;
        // nums2를 순회하며 해시 테이블에 있는 원소를 결과에 추가
        for (int num : nums2) {
            if (count[num] > 0) {
                result.push_back(num);
                count[num]--;
            }
        }
        
        return result;
    }
};