[JS] 부분집합 여부 파악하기

✔ 문제

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

✔ 주의 사항

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

내가 푼 방법

1. 이중 반복문을 이용해 값이 같은 요소인지 확인

const isSubsetOf = function (base, sample) {
  for(let i of base) {
    for(let j of sample) {
      if(i === j) {
        return true;
      }
      else return false;
    }
  }
};

해당 경우 정렬되지 않은 배열이 올 경우 오류를 발생시킨다.

2. 주어진 배열을 정렬해 같은 요소인지 확인

const isSubsetOf = function (base, sample) {
  base.sort((a, b) => a - b);
  sample.sort((a, b) => a - b);
  for(let i of base) {
    for(let j of sample) {
      if(i === j) {
        return true;
      }
      else return false;
    }
  }
};

해당 경우 순서에 상관없는 배열의 경우도 통과할 수 있지만 시간 복잡도 항목을 통과하지 못했다.
내가 생각한 2가지 방법은 모두 이중 반복문을 사용해 주의 사항의 조건을 충족시키지 못하였다. 시간복잡도를 생각한 코드는 어떻게 짜는 것이 좋을까?

개선된 코드

const isSubsetOf = function (base, sample) {
  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;
};

먼저 주어진 배열을 sort를 통해 정렬한다. 처음 값이 일치하는 요소의 index를 저장(baseIndex)한 후 다음 요소를 탐색할 때 해당 index (baseIdx)부터 탐색을 시작한다. 이 코드의 경우 값이 일치하지 않는 요소의 경우 더 이상 비교를 하지 않고 종료하기 때문에 복잡도 문제가 해결되는 것이다.