메서드의 시간복잡도를 생각할 것 (slice)

부분집합인지 확인하는 함수를 작성해보라는 코드문제
ex) [1,2,3,4][1,2] => true

const isSubsetOf = function (base, sample) {
  // TODO: 여기에 코드를 작성합니다.
  base.sort((a, b) => a - b);
  sample.sort((a, b) => a - b);
  for(let i = 0; i < sample.length; i++){
    if(base.includes(sample[i])){
      base = base.slice(base.indexOf(sample[i])+1)
    } else if(!base.includes(sample[i])){
      return false
    }
  }
  return true
};

sample 배열의 모든 항목을 조사하는데,
항상 base의 첫번째부터 비교할 필요는 없다.
두 배열을 오름차순으로 모두 정렬했다면 방금 확인했던 부분 부터 이어서 확인하면 된다.
나는 그래서 'slice로 확인이 된 곳 까지 잘라내면 구현되겠다' 라고 생각했다.

여기서 내가 망각한 것은 slice도 시간 복잡도가 있는 것이다.
slice의 시간 복잡도는 처음부터 끝까지 복사해서 잘라내야하기 때문에 O(n)이 된다.

결국 나는 inlcudes의 시간 복잡도 O(n)이라는 부분을 해결하기 위해 slice를 사용했지만
slice 또한 O(n)이기 때문에 사실상 의미가 없다.

배열의 인덱스를 저장해 뒀다가 거기서부터 이어서 봐야한다. 고차함수로 가야한다.
아래는 정확한 풀이

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;
  };
  // from이라는 친구가 어디에서부터 시작할지 정해줌

  let baseIdx = 0;
  for (let i = 0; i < sample.length; i++) {
    baseIdx = findItemInSortedArr(sample[i], base, baseIdx);
    if (baseIdx === -1) return false;
  }
  return true;
};
// findItemSortedArr 함수를 통해서 찾은데까지 index를 반환
// 반환된 indexfmf baseIdx에 저장하고 for문 돌리기
// -1 반환은 배열안에 없을 경우 => 즉시 리턴 조건