[Algorithm] _isSubsetOf

문제

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

입력

인자 1 : base

number 타입을 요소로 갖는 임의의 배열

base.length는 100 이하

인자 2 : sample

number 타입을 요소로 갖는 임의의 배열

sample.length는 100 이하

출력

boolean 타입을 리턴

입출력 예시

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

Advanced

시간 복잡도를 개선하여, base / sample 길이가 70,000 이상인 테스트 케이스를 통과해라

---

문제 자체는 간단하지만, 시간 복잡도를 고려해야해서 다소 어렵게 느껴진 문제였다. 배열을 여러번 순회하면 시간 복잡도가 매우 커지기 때문에, 최소한의 탐색으로 부분집합 여부를 찾아내는 것이 관건이었다. 연산 횟수를 줄이기 위해 필요한 핵심 스킬(?)들이 있었다.

1. 배열을 오름차순 정렬, 순회하는 요소가 찾는 값보다 크면 찾는 값이 없는 것이므로 반복문을 종료한다.
2. sample의 요소를 base에서 찾았다면, 다음으로 찾는 값은 해당 요소보다 크기 때문에 해당 요소의 인덱스부터 base를 순회한다.

이를 적용한 코드는 다음과 같다.

const isSubsetOf = function (base, sample) {
  
  // * 1-1) 배열을 오름차순 정렬
  base.sort((a, b) => a - b);
  sample.sort((a, b) => a - b);
	
  // base에서 sample의 요소를 찾는 함수
  const findItemInSortedArr = (item, arr, from) => {
    for (let i = from; i < arr.length; i++) {
      
      // 찾으면, 해당 인덱스를 리턴
      if (item === arr[i]) return i;
      
      // * 1-2) 순회하는 요소가 찾는 값보다 크면 -1을 리턴 
      else if (item < arr[i]) return -1;
    }
    
    // 마지막까지 찾지 못하면 -1을 리턴
    return -1;
  };

  // 반복문 시작 인덱스
  let baseIdx = 0;
  
  // sample의 모든 요소를 순회하여 base에서 일치하는 값을 찾는다
  for (let i = 0; i < sample.length; i++) {
    
   // * 2) 같은 값을 찾으면 해당 인덱스부터 반복문을 실행한다  
    baseIdx = findItemInSortedArr(sample[i], base, baseIdx);
    
    // 하나라도 찾지 못하면 부분집합이 아니기 때문에 false를 리턴
    if (baseIdx === -1) return false;
  }
  
  // 모두 찾으면 true를 리턴
  return true;
};