[JS] isSubsetOf

입력

인자1: base

Number타입을 요소로 갖는 길이 100이하의 배열

인자2: sample

Number타입을 요소로 갖는 길이 100이하의 배열

출력

인자sample이 base의 부분집합인지의 여부의 boolean타입

주의사항

sample와 base내에 중복되는 요소는 없다.

수도코드

Array 내장 메서드 evey와 includes를 사용하면 쉽게 풀 수 있다.

const isSubsetOf = function (base, sample){
  return sample.every((number) => base.includes(number));
}

하지만 모든 요소를 확인하기 때문에 테스트의 실행 시간을 초과하게 된다.

시간 복잡도를 개선하기 위해

• 인자 배열의 요소를 오름차순으로 정렬한다.
• 이미 확인한 요소는 다시 확인하지 않는다.
• base의 요소를 반복하면서 simple의 요소를 갖고 있지 않는 반복이 있는 순간 반복을 멈추고 false를 반환한다.

base와 sample의 요소를 오름차순으로 정렬한다.

base.sort((a, b) => a - b);
sample.sort((a, b) => a - b);

arr의 요소와 item을 from 부터 비교할 함수를 만든다.

const findItemInSortedArr = (item, arr, from) => {}

-> from 부터 arr의 길이까지 반복하는 문

for (let i = from; i < arr.length; i++) {}

--> item이 arr의 요소와 같을 경우 현재 인덱스를 리턴

if (item === arr[i]) return i;

--> item이 arr의 요소보다 클 경우 -1을 리턴

else if (item < arr[i]) return -1;

인자 from으로 인해 작은수를 비교하지 않아도 된다.

-> 반복이 끝나도 return 되지 않았으면 -1을 리턴

return -1;

이제 base의 요소를 반복하면서 simple의 요소를 갖고 있지 않는 반복이 있는 순간 반복을 멈추고 false를 반환한다.

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

이 반복문이 지나도 리턴이 안됬으면 true를 리턴

return true;

코드

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;
};