부분집합 확인 Javascript

부분집합인지 확인하는 문제

두 개의 배열(base, sample)을 입력받아 sample이 base의 부분집합인지 여부를 반환하라.

for문을 통해 문제를 해결하려한다면 시간복잡도를 고려하지 않았기 때문에, 다른 방법으로 접근해야한다.

우선 sample이 base의 부분집합인지 확인을 하는 문제이기 때문에 2개의 배열 모두 정렬시킨다.
이후 base를 탐색할 때 특정범위만 탐색해야한다.

일치하는 인덱스값을 저장 후 요소를 탐색할 때 저장된 값을 사용해 문제를 해결하자.

// subsetOf는 부분집합을 뜻한다.
function solution(base, sample) {
  base.sort((a, b) => a - b);
  sample.sort((a, b) => a - b);

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

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