leetcode 알고리즘 - Intersection of Two Arrays II

두 배열에서 겹치는 부분을 찾아내는 문제다.

 

Given two arrays, write a function to compute their intersection.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

답은 이렇다.

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function (nums1, nums2) {
  nums1.sort((a, b) => b - a); // 내림차
  nums2.sort((a, b) => b - a); // 내림차

  const result = [];

  if (nums1.length < nums2.length) {
    nums1.map((v) => {
      const num2 = nums2.indexOf(v); // 앞에서부터 찾는다.
      if (num2 !== -1) {
        nums2.splice(num2, 1);
        result.push(v);
      }
    })
  } else {
    nums2.map((v) => {
      const num2 = nums1.indexOf(v); // 앞에서부터 찾는다.
      if (num2 !== -1) {
        nums1.splice(num2, 1);
        result.push(v);
      }
    })
  }
  return result;
};

 

 

하나씩 살펴본다.

 

겹치는 값이 있는지 찾으려면 더 작은 배열에 있는 값이 더 큰 배열에 있는지를 확인하면 된다.

 

먼저 내림차순으로 sort 한다.

sort 하고 순서대로 값을 찾는다.

문제에서는 중복된 값을 허용한다.

 

1, 2, 2, 1 과 2,2 의 경우 답이 2,2 이다.

 

그래서 값을 찾을때마다 배열에서 없애기로 했다.

nums1.map((v) => {
      const num2 = nums2.indexOf(v); // 앞에서부터 찾는다.
      if (num2 !== -1) {
        nums2.splice(num2, 1);
        result.push(v);
      }
    })

배열 1에서 배열 2에 해당 값이 있는지 찾는다.

찾았다면 배열 2에서 항목을 제거한다.

그리고 값을 결과 배열에 push 한다.

 

2,2 에서 2,2,1,1 을 찾는 경우

 

이렇게 하면 첫번째 2가 제거된다.

두번째 2도 배열에 있는지 확인한다.

남은 2가 발견된다. 제거한다.

 

그리고 nums1에 다른 항목이 없으므로 map 문을 종료한다.

 

[2,2]가 결과로 리턴된다.