두 배열의 교차점을 구하는 방법

종종 면접관은 믿을 수 없을 정도로 쉬운 일로 당신을 테스트합니다. 우리는 이것을 Reverse a String에서 보았고 향후 도전에서 더 많이 보게 될 것입니다. 그러나 때로는 약간 사소하지만 일상적인 소프트웨어 엔지니어링에 정말 유용한 개념에 대해 테스트를 받을 수도 있습니다.

그 중 하나는 array manipulation 또는 기본적으로 어떤 종류의 변환을 생성하는 array에 대한 작업입니다.

즉각적인

두 개의 배열을 입력으로 사용하고 교차점을 반환하는 함수를 작성할 수 있습니까? 교차점을 배열 형태로 반환해 봅시다.



최종 결과의 모든 요소는 고유해야 합니다. 다음은 한 가지 예입니다.

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

intersection(nums1, nums2);
// [2]

그리고 여기 또 다른 것이 있습니다:

const nums1 = [4,9,5];
const nums2 = [9,4,9,8,4];

intersection(nums1, nums2);
// [9, 4]

이 강의는 원래 https://algodaily.com에 게시되었으며, 여기서 저는 기술 인터뷰 과정을 유지하고 야심찬 개발자를 위한 아이디어를 작성합니다.

브루트 포스

문제의 구성을 조사하기 위해 가능한 가장 작은 샘플 입력을 사용하여 천천히 시작할 것입니다. 반환하려면 result 배열이 필요하다는 것을 알고 있으므로 다음 사항을 염두에 두십시오.

const results = [];

[1] 및 [1] 두 배열의 교차점을 찾아야 한다고 가정해 보겠습니다. 이 경우 출력도 [1]임을 알고 있습니다. 1와 1를 직접 비교하기만 하면 되기 때문에 다소 간단합니다. 첫 번째 [1] 를 살펴보고 1 를 보고 두 번째 배열에서 찾습니다. 그것들은 동일하기 때문에 해당 일치와 함께 result만 반환합니다.

그래서 우리는 이것을 넘어 확장해야 합니다. 두 개의 입력이 [1] 및 [2] 로 수정되었다고 가정해 보겠습니다. 글쎄, 우리가 두 개의 단일 요소를 비교할 때, 우리는 그들이 동일하지 않다는 것을 압니다. 따라서 우리는 result 로 아무 것도 할 필요가 없습니다.

이것이 하나의 배열 요소를 넘어 계속됨에 따라 첫 번째 배열의 각 요소가 두 번째 배열에 존재하는지 확인하는 이 프로세스를 계속할 수 있습니다.

let intersection = firstArray.filter((el) => {
  return secondArray.includes(el);
};

교집합의 개념은 집합론에서 나온 것이므로 이 문제는 Set만 사용하면 정말 간단합니다! 수학에서 두 집합 A와 B의 교집합은 B에도 속하는 A의 모든 요소를 ​​포함하는 집합입니다.
Set s는 대부분의 기본 형식의 고유한 값을 저장할 수 있는 대부분의 언어에서 객체 유형입니다.

입력 배열을 집합으로 변환하면 filter 방법을 사용할 수 있고 집합 중 하나에 적용하여 다른 집합에 없는 것을 필터링할 수 있습니다.

function intersection(nums1, nums2) {
  const set = new Set(nums1);
  const fileredSet = new Set(nums2.filter((n) => set.has(n)));
    return [ ...fileredSet ];
}

시간복잡도는 O(n) 입니다.

다른 방법은 Set 를 사용하지 않고 입력을 모델링하기 위해 배열을 유지하는 것입니다. 이 접근 방식에서는 고유성을 보장하기 위해 해시Object도 필요합니다. 이것은 객체 키가 고유해야 하기 때문에 작동합니다.
indexOf 검사를 수행한 다음 배열 형식으로 반환하여 고유한 교차점을 수집할 수 있습니다.

function intersection(nums1, nums2) {
    let intersection = {};

    for (const num of nums1) if (nums2.indexOf(num) !== -1) intersection[num] = 1;

    return Object.keys(intersection).map((val) => parseInt(val));
}

두 가지 방법이 있지만 인터뷰 중에 비슷한 문제가 발생하면 Set를 사용하는 것이 도움이 될 수 있습니다. 일반적으로 사용되는 data structure에 대한 지식과 수학에 대한 배경 지식을 보여주기 때문입니다.

technical challenges at AlgoDaily.com에 대한 더 많은 시각적 자습서를 확인하고 our daily coding problem newsletter을 사용해 보십시오!