24_isSubsetOf

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

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

//입출력 예시
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) {
  // TODO: 여기에 코드를 작성합니다.
  // 각 배열을 정렬: 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++) { //시작하는 인덱스 baseIdx로 조정, -1이 아니라면 아니었던 그 요소부터 배열시작
      if (item === arr[i]) return i; //찾고자하는 요소와 목표값이 같다면 -1이 아닌 숫자 리턴
      else if (item < arr[i]) return -1; //찾고자하는 요소보다 목표값이 작다면 -1리턴
    }
    return -1; //찾고자하는 요소보다 목표값이 크다면 -1리턴
  };

  let baseIdx = 0;
  for (let i = 0; i < sample.length; i++) {
    baseIdx = findItemInSortedArr(sample[i], base, baseIdx); //sample요소와 base요소를 비교하고 시작 인덱스는 둘의 요소가 같았던 base인덱스에서 다시 시작
    if (baseIdx === -1) return false; //sample의 요소가 base의 요소를 다 뒤졌는데도 없으면 false리턴에서 멈춤
  }
  return true; //마지막까지 false에 걸리지 않았다면 true리턴
};


/*
//처음 생각한 코드 : 시간복잡도 고려하지 않아 실행시간을 초과
const isSubsetOf = function (base, sample) {
  sample = sample.filter(v => base.includes(v) ? 1:2);
  return sample.includes(2) ? false:true;
};

//두번째 방법 : 실행시간 초과
const isSubsetOf = function (base, sample) {
  let result = [];
  for(let a of sample){
    for(let b of base){
      if(a===b) result.push(b);
    }
  }
  return result.length===sample.length ? true:false;
};

//레퍼런스 방법 : 실행시간 초과
const isSubsetOf = function (base, sample) {
  return sample.every((item) => base.includes(item));
};
//every()메서드는 배열안의 모든 요소가 주어진 판별함수를 통과하는지 테스트하고 boolean값을 반환한다.
 */