[Leet code - 349] Intersection of Two Arrays ✅

Intersection of Two Arrays - LeetCode

문제

Input : 정수 배열 nums1, nums2
Output : 두 배열의 동일한 원소를 담은 배열

※ 결과 각 원소는 한 번만 포함되며, 순서는 상관없다.

 

 

시간 복잡도

※1초에 1억 번을 대략적인 기준으로 삼는다.

$1 \le nums1.length, nums2.length \le 1000$

$O(n) = nums1. length + nums2. length = 2000$
즉, 대략 $n^2$이하의 복잡도를 사용할 수 있다.

 

해결 과정

num1의 원소를 순회하면서 set에 저장한다.

set의 특성상 같은 키를 추가하여도 의미가 없어지기 때문에 중복이 알아서 제거되기 때문에 set을 사용하려고 했다.

num2를 순회하면서 각 원소가 set에 있는지 확인하고, 있다면 결과 배열에 추가한다.

추가를 한다면 중복 처리를 막기 위해 set에서 삭제를 해주어야 한다고 생각했다.

 

 

구현

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) 
{
    vector<int> ret;
    ret.reserve(1001);

    // store unique elements from nums1
    unordered_set<int> set;
    for (int d : nums1)
        set.insert(d);

    for (int d : nums2)
        // return value of erase : find and delete = 1 | not find = 0
        if(set.erase(d) == 1) ret.push_back(d);

    return ret;
}

 

 

되돌아보기

• 핵심 아이디어
  한 배열을 set으로 만들고 다른 배열을 순회하면서 set을 조회 하는 것이다.
• set의 역할
  중복 없는 원소 저장 + 빠른 조회
• erase 반환 값
  처음에는 값이 있는지 확인하고 있다면 push하고... 이런 식으로 사용했으나, 좀 더 깔끔하게 할 수 있지 않을까? 했었다.
  그래서 보통 함수에 결과 값을 반환하는 함수도 있으니까 erase가 만약 결과 값을 반환한다면 이용할 수 있겠다 싶었다.
  
  찾아본 결과 찾아서 지웠다면 1, 못 찾았다면 0를 반환하기 때문에, 이를 이용하여
  if(set.find(n)) 과 set.erase(n)을 한 줄로 축약할 수 있었다.