Toy_#3. isSubsetOf

- 문제:

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

입출력 예시:

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

풀이:

naive한 풀이는 이중 for문을 사용하거나 sample 요소 하나씩 indexOf를 사용하여 base 배열에 확인해 보면 되겠지만, 이는 모두 효율적인 방법이 아니다.

base와 sample 모두 요소의 숫자 순으로 정렬을 하고, sample의 첫 번째 요소가 발견된 base의 index 번호 다음부터 조회가 될 수 있도록 하면 효율적인 방법으로 조회를 할 수 있다.

const isSubsetOf = function (base, sample) {
  base = base.sort((a, b) => a - b);
  sample = sample.sort((a, b) => a - b);
  // 요소의 숫자 순으로 정렬해준다.
  
  // 1. 재귀함수를 생성한다. 이 재귀함수때문에 sample 요소값이 base에서 찾아지면 해당 요소의 다음 요소부터 조회를 하는 조건이 생성된다
  const aux = function(item, arr, idx) {
    for (let i = idx; i < arr.length; i++) {
      if (item === base[i]) {
        return i + 1 // 바로 요기가 그 조건이다.
      } else if (item < arr[i]) return -1;
    }
    return -1;
  }
  
  // 2. base 요소의 for문을 돌리면서 재귀함수안에 base와 인덱스 값을 인자로 전달한다. 
  // 업데이트되는 base의 인덱스와 base 배열을 계속 가지고 다니며 sample 요소 값을 비교할 수 있다.
  let idx = 0;
  for (let i = 0; i < base.length; i++) {
    idx = aux(sample[i], base, idx); 
    if (idx === -1) { // sample이 base에서 안 찾아지면 바로 -1를 반환한다. 이는 부분 집합의 요소가 없다는 것을 의미하므로 false를 반환한다.
      return false;
    }
    return true;
  }
}