두 개의 배열(base, sample)을 입력받아 sample이 base의 부분집합인지 여부를 리턴해야 합니다.

isSubsetOf

문제

두 개의 배열(base, sample)을 입력받아 sample이 base의 부분집합인지 여부를 리턴해야 합니다.

입력

인자 1 : base

• number 타입을 요소로 갖는 임의의 배열
• base.length는 100 이하

인자 2 : sample

• number 타입을 요소로 갖는 임의의 배열
• sample.length는 100 이하

출력

• boolean 타입을 리턴해야 합니다.

주의사항

• base, sample 내에 중복되는 요소는 없다고 가정합니다.

입출력 예시

let base = [1, 2, 3, 4, 5];
let sample = [1, 3];
let output = isSubsetOf(base, sample);
console.log(output); // --> true

sample = [6, 7];
output = isSubsetOf(base, sample);
console.log(output); // --> false

base = [10, 99, 123, 7];
sample = [11, 100, 99, 123];
output = isSubsetOf(base, sample);
console.log(output); // --> false

Advanced

• 시간 복잡도를 개선하여, Advanced 테스트 케이스(base, sample의 길이가 70,000 이상)를 통과해 보세요.

문제풀이

1. 먼저 입력받은 인자들이 배열이 아닐경우 false로 예외처리로 빼고 시작한다. 

const isSubsetOf = function (base, sample) {
  // 입력값이 배열이 아닌 경우 false 반환
  if (!Array.isArray(base) || !Array.isArray(sample)) {
    return false;
  }
}

2. base 배열의 요소들을 중복을 제거하여 Set 객체 baseSet에 저장한다.

const isSubsetOf = function (base, sample) {
  // 입력값이 배열이 아닌 경우 false 반환
  if (!Array.isArray(base) || !Array.isArray(sample)) {
    return false;
  }
  const baseSet = new Set(base);
}

3. sample 배열의 각 요소들이 baseSet 객체에 존재하는지 검사하고 for...of 구문을 사용하여 sample 배열을 순회하면서, baseSet 객체에 value가 존재하지 않으면 false를 반환시킨다.

const isSubsetOf = function (base, sample) {
  // 입력값이 배열이 아닌 경우 false 반환
  if (!Array.isArray(base) || !Array.isArray(sample)) {
    return false;
  }

  // Set 객체 생성
  const baseSet = new Set(base);

  // sample 배열의 각 요소가 baseSet에 존재하는지 확인
  for (const value of sample) {
    // baseSet에 존재하지 않는 요소가 있으면 false 반환
    if (!baseSet.has(value)) {
      return false;
    }
  }
}

4. sample 배열의 모든 요소들이 baseSet 객체에 존재하면, true를 반환시킨다. 검사가 끝나면 for...of 구문을 벗어나서 true를 반환한다.

const isSubsetOf = function (base, sample) {
  // 입력값이 배열이 아닌 경우 false 반환
  if (!Array.isArray(base) || !Array.isArray(sample)) {
    return false;
  }

  // Set 객체 생성
  const baseSet = new Set(base);

  // sample 배열의 각 요소가 baseSet에 존재하는지 확인
  for (const value of sample) {
    // baseSet에 존재하지 않는 요소가 있으면 false 반환
    if (!baseSet.has(value)) {
      return false;
    }
  }

  // 모든 요소가 baseSet에 존재하면 true 반환
  return true;
};

정리)  base 배열의 요소들을 Set 객체 baseSet에 저장시키고 sample 배열의 각 요소들이 baseSet 객체에 존재하는지 검사하여, 모든 요소가 baseSet 객체 내에 존재하면 true를 반환하고, 그렇지 않으면 false를 반환한다.

• Set 객체는 ES6에서 추가된 내장 객체로, 중복되지 않는 값을 저장할 수 있는 객체다.
• Set 객체를 생성할 때, 인자로 전달한 배열의 요소들을 자동으로 중복 제거하여 저장한다.
• Set 객체는 has() 메서드를 제공하며 has() 메서드는 인자로 전달한 요소가 Set 객체 내에 존재하는지 검사하여 true/false 값을 반환한다.

위 코드의 시간복잡도는 Set()을 사용하여 검색 시간을 O(1)로 줄일 수 있었다.

---

위 코드 전에 includes 메서드와 for ... of 구문을 사용하여 sample 배열을 순회하면서 base 배열에 value가 존재하지 않으면 false를 반환하고, 모든 요소가 base 배열에 존재하면 true를 반환시키는 코드를 작성했을때도 O(N)이였는데 통과되지 않았다.

const isSubsetOf = function (base, sample) {
  if (!Array.isArray(base) || !Array.isArray(sample)) {
    return false;
  }

  for (const value of sample) {
    if (!base.includes(value)) {
      return false;
    }
  }

  return true;
};

그래서 includes 메서드가 내부적으로 indexOf를 사용하기 때문에 더 빠르게 실행될 수 있다고 하기에 아래와 같이 indexOf 메서드를 사용하는 방식으로 코드를 수정해보았다.

const isSubsetOf = function (base, sample) {
  if (!Array.isArray(base) || !Array.isArray(sample)) {
    return false;
  }

  for (const value of sample) {
    if (base.indexOf(value) === -1) {
      return false;
    }
  }

  return true;
};

includes 메서드보다 더욱 빠른 실행 속도(O(N))로 작동한다고 하는데 역시나 통과되지는 않았다..  하지만 정상적으로 작동은 한다.

---

문제풀이2

const isSubsetOf = function (base, sample) {
  // base와 sample 모두 배열이 아니거나, base가 sample보다 짧은 경우 false를 반환
  if (!Array.isArray(base) || !Array.isArray(sample) || base.length < sample.length) {
    return false;
  }

  // base와 sample 배열을 정렬
  const sortedBase = base.sort();
  const sortedSample = sample.sort();

  let i = 0;
  let j = 0;

  // sortedBase와 sortedSample 배열에서 동일한 요소를 찾을 때까지 반복
  while (i < sortedBase.length && j < sortedSample.length) {
    if (sortedBase[i] < sortedSample[j]) {
      i++;
    } else if (sortedBase[i] > sortedSample[j]) {
      j++;
    } else {
      i++;
      j++;
    }
  }

  // sortedSample 배열의 모든 요소가 sortedBase 배열에 존재하면 true를 반환
  return j === sortedSample.length;
};

먼저 base 배열과 sample 배열을 정렬하고. 두 배열에서 동일한 요소를 찾기 위해 변수 i와 j를 사용. i는 sortedBase 배열의 인덱스, j는 sortedSample 배열의 인덱스 알 수 있도록.

그리고 sortedBase[i]가 sortedSample[j]보다 작으면, i를 증가시켜 다음 sortedBase 요소를 확인시킨다. sortedBase[i]가 sortedSample[j]보다 크면, j를 증가시켜 다음 sortedSample 요소를 확인시키고 sortedBase[i]와 sortedSample[j]가 동일하면, i와 j를 모두 증가시켜 다음 요소를 확인시킨다.

이러한 반복문을 다 끝내고, sortedSample 배열의 모든 요소가 sortedBase 배열에 존재하면 true를 반환한다.

---

레퍼런스코드

const isSubsetOf = function (base, sample) {
  // naive solution: O(M * N)
  // return sample.every((item) => base.includes(item));

  // 각 배열을 정렬: O(N * logN), O(M * logM)
  // N >= M 이므로, O(N * logN)
  base.sort((a, b) => a - b);
  sample.sort((a, b) => a - b);

  const findItemInSortedArr = (item, arr, from) => {
    for (let i = from; i < arr.length; i++) {
      if (item === arr[i]) return i;
      else if (item < arr[i]) return -1;
    }
    return -1;
  };

  let baseIdx = 0;
  for (let i = 0; i < sample.length; i++) {
    baseIdx = findItemInSortedArr(sample[i], base, baseIdx);
    if (baseIdx === -1) return false;
  }
  return true;
};