20.12.17 isSubsetOf_algorithms

isSubsetOf

두 개의 배열(base, sample)을 입력받아 sample이 base의 부분집합인지 여부를 리턴해야 합니다.
인자 1 : base
number 타입을 요소로 갖는 임의의 배열 (base.length <= 100 )
인자 2 : sample
number 타입을 요소로 갖는 임의의 배열 (sample.length <= 100 )

• base, sample 내에 중복되는 요소는 없다고 가정합니다.
• 시간 복잡도를 개선하여, 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

부분집합 여부에 대한 알고리즘 문제이다.
base와 sample을 sort 메소드로 작은 수 부터 정렬을 먼저 시킨다음
재귀함수를 만든다.

이 재귀함수는 (찾을 것, 찾아야하는 것의 모음, 레벨)을 인자로 받고
(반복)찾을 것의 모음 수량 만큼 반복을 하면서
(만약)찾는 것이 있다면 찾는 것을 리턴하고 함수를 종료한다.
(!만약)찾는 것이 없다면 -1을 리턴하고 종료.

이번엔 (반복) 찾을 것들을 반복하면서
0부터 시작해서 재귀함수를 호출한다.
(만약) 재귀의 결과가 -1이 리턴되면 false로 종료

아니라면 다 true로 종료

const isSubsetOf = function (base, sample) {
  // 0부터 n까지 반복하기 위해 정렬시킴
  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++) {
      // i가 리턴 되면 이 i는 baseIdx가 된다.
      if (item === arr[i]) return i;
      else if (item < arr[i]) return -1;
    }
    return -1;
  };

  // 이 baseIdx는 재귀의 레벨(초기화 0)
  let baseIdx = 0;
  for (let i = 0; i < sample.length; i++) {
    baseIdx = findItemInSortedArr(sample[i], base, baseIdx);
    // 만약 찾는 것이 없어서 -1이 되면 false로 리턴
    if (baseIdx === -1) return false;
  }
  // 아니면 다 true로 리턴
  return true;
};