toy problem 03

isSubsetOf

문제

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

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

 

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++) { // 샘플의 값을 돈다.
  // sample의 요소가 base에 들어있는지 판별해주는 함수를 선언한다.
    baseIdx = findItemInSortedArr(sample[i], base, baseIdx);
    
    if (baseIdx === -1) return false;
  }
  return true;
};

 

let base = [1, 2, 3, 4, 5];
let sample = [1, 3];

baseIdx = 0
for(sample.length)를 돈다
첫번째 for
baseIdx = findItemInSortedArr(sample[0],base,0)
baseIdx === -1인 경우 return false
baseIdx i인 경우 ex)[1,3]
두번째 for
baseIdx = findItemInSortedArr(sample[1],base,0)