[Leetcode/C++] 349_Insertion_of_Two_Arrays

문제링크: https://leetcode.com/problems/intersection-of-two-arrays

문제는 다음과 같습니다.

먼저 저는 이 문제를 풀때, 해쉬를 써야겠다고 생각을 해서 unordered_map을 이용하였습니다.
거의 비슷한 두 가지 방법으로 풀었는데, 풀이는 다음과 같습니다.

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        nums1.erase(unique(nums1.begin(), nums1.end()), nums1.end());
        nums2.erase(unique(nums2.begin(), nums2.end()), nums2.end());
        
        unordered_map<int, int> um;
        for(int i=0; i<nums1.size(); i++) um[nums1[i]]++;
        for(int i=0; i<nums2.size(); i++) um[nums2[i]]--;
        
        vector<int> res;
        for(auto elem: um){
            if(elem.second == 0){
                res.push_back(elem.first);
            }
        }
        return res;
    }
};

이 방법은 먼저,
주어진 벡터 nums1과 nums2에서 중복된 원소를 제거합니다.

그리고 unordered_map을 이용하여, 벡터 nums1에 있는 값들은 ++을 해주었고, nums2에 있는 값들은 --을 해주었습니다.
결과적으로 intersection은 um의 키에 해당하는 value가 0인 키의 값들만 모으면 됩니다.

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> um;
        vector<int> res;
        for(int i=0; i<nums1.size(); i++) um[nums1[i]]++;
        
        for(int i=0; i<nums2.size(); i++){
            if(um[nums2[i]]>0) res.push_back(nums2[i]);
        }
        sort(res.begin(), res.end());
        res.erase(unique(res.begin(), res.end()), res.end());
        
        return res;
    }
};

두번째 방법도 해쉬를 이용한 비슷한 방법입니다.
여기서는 벡터에서 중복 제거를 맨 뒤에서 한 번 해주었습니다.

Discussion에서 다른 풀이도 같이 함께 비교해보겠습니다!

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    set<int> st;        
    for(int itr = 0; itr < nums1.size(); itr++){
        for(int jtr = 0; jtr < nums2.size(); jtr++){
            if(nums1[itr] == nums2[jtr]){
                st.insert(nums1[itr]);
                break;
            }
        }
    }
    
    vector<int> vt;
    for(auto itr = st.begin(); itr != st.end(); itr++){
        vt.push_back(*itr);
    }
    return vt;
}

c++의 set container를 이용한 방법입니다!
그러게요,, 굳이 중복을 제거할 필요없이 set을 갖다 쓰면 더 간단하게 풀 수 있었네용

입력받은 두 벡터에서 같은 값이 존재할 경우 이를 set에 넣어주고, 값이 중복되더라도 어차피 set은 중복이 허용되지 않기때문에 하나의 값만 저장이됩니다!
그리고 마지막에 이 set의 원소들을 모두 결과벡터에 넣어서 이를 반환하면 됩니다!

또 다른 풀이도 함께 살펴보겠습니다.

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> st(nums1.begin(), nums1.end());
        vector<int> res;
        for(int itr = 0; itr < nums2.size(); itr++){
            if(st.find(nums2[itr]) != st.end()){
                res.emplace_back(nums2[itr]);
                st.erase(nums2[itr]);
            }            
        }
        return res;
 }

두 번째 풀이가 첫 번째 풀이보다 더 빠른 것 같습니다.
첫 번째 풀이의 시간복잡도는 O(n*m)이지만, 두 번째에서는 O(n)이기 때문입니다.
오,, 저렇게 set st(nums1.begin(), nums1.end()); 으로 해서 set을 한번에 초기화할수도 있군요.. 신기합니당
그래서, 두 번째 벡터만 순회하면서 벡터에 nums2의 값이 존재할 경우, 결과벡터에 이에 해당하는 원소를 넣어 이를 반환하는 방법입니다!
이번에 stl책도 샀는데,, stl 열심히 공부하겠습니다☺️☺️

풀이추가)

  class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans; // Initialize an empty vector to hold the result
        set s = set(nums1.begin(), nums1.end()); // Storing elements of first array into a set, so we can get rid of duplicacy
        
        for(int x: nums2) // Iterate through the elements of second array
		{
            if(s.find(x) != s.end()) // Check if the element of second array is present in the set created from first array
			{
                ans.push_back(x); // push matched element into result
                s.erase(x); // remove element from the set, so we will not face any duplicacy in the next iteration
            }
        }
        return ans;
    }
};

풀이에 해당하는 링크는 여기에 남겨두겠습니다.
[링크] https://leetcode.com/problems/intersection-of-two-arrays/discuss/1015238/4-Approaches-O(N)-Easy-to-understand-C%2B%2BJava
링크