[Leetcode][자바스크립트][Easy] 350. Intersection of Two Arrays II

풀이1

/**
 * 350_IntersectionOfTwoArraysII.js
 * Easy
 * https://leetcode.com/problems/intersection-of-two-arrays-ii/
 */
 
 var intersect = function(nums1, nums2) {
    const answer = [], idxHash = {}; 

    nums1.forEach((num) => {
        const idx = idxHash[num] === undefined ? nums2.indexOf(num) : nums2.indexOf(num, idxHash[num] + 1);
        if (idx > -1) {
            idxHash[num] = idx;
            answer.push(num);
        }
    });
    
    return answer;
};

교집합을 구하는 문제로 hash 에 기존에 존재했던 값의 index 를 넣어두고 다음에 같은 값을 만났을 때 index + 1 부터 indexOf 로 해당 값이 있는지 확인하는 방식으로 해결했다.

 

풀이2 - 최적화

/**
 * 350_IntersectionOfTwoArraysII.js
 * Easy
 * https://leetcode.com/problems/intersection-of-two-arrays-ii/
 */
 
 var intersect = function(nums1, nums2) {
    let small, big, answer = [], idxHash = {}; 
    if (nums1.length <= nums2.length) {
        small = nums1;
        big = nums2;
    } else {
        small = nums2;
        big = nums1;
    }  

    small.forEach((num) => {
        const idx = idxHash[num] === undefined ? big.indexOf(num) : big.indexOf(num, idxHash[num] + 1);
        if (idx > -1) {
            idxHash[num] = idx;
            answer.push(num);
        }
    });
    
    return answer;
};

해결 방법은 첫 번째 풀이와 동일하고, 교집합을 구하는 문제이므로 길이가 짧은 배열을 기준으로 겹치는 값을 찾으면 길이가 긴 배열을 기준으로 찾을 때보다 두 배열의 길이 차이만큼 연산 수를 줄일 수 있다.