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

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

풀이

1. 재귀로 시도

const isSubsetOf = function (base, sample) {

  if(sample.length === 0) return false;

  const checkValue = sample[0];
  
  for(let i=0;i<base.length;i++){
    if(base[i] === checkValue)  return true;
  }

  return isSubsetOf(base, sample.slice(1));
};

✅ 문제 풀때는 안보였던 문제점이 이제서야 보이네!
위에 짠 코드의 경우, sample 배열안의 요소 중 하나라도 base와 같다면 return true가 되어 버림!

➡️ false가 나와야 하지만 true값이 리턴이 되어버림

---

2. 시간복잡도를 고려한 코드

const isSubsetOf = function (base, sample) {

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

  for(let i=0;i<base.length;i++){
    if(base[i] === sample[0]){
      sample.shift();
    }
    if(sample.length === 0) return true;
  }

  return false;
};


/*

# CASE 1

base = [10, 99, 123, 7];
sample = [11, 100, 99, 123];

1. sort() 메소드를 적용한 이후,
base = [7, 10, 99, 123]
sample = [11, 99, 100, 123]

2. for문 시작
i = 0  =>  base[0] =   7, sample[0] = 11
i = 1  =>  base[1] =  10, sample[0] = 11
i = 2  =>  base[2] =  99, sample[0] = 11
i = 3  =>  base[3] = 123, sample[0] = 11

3. for문 종료 후, return false

* 부분집합 = 부분집합의 모든 요소가 상위 요소에 포함 되어 있어야 함
=> sample의 모든 배열 값이 base에 포함이 되어 있어야만 true
=> sample[0]을 기준 삼아 base의 모든 요소를 for문으로 돌려 
그 값이 base에 포함되어 있는지 없는지를 체크

# CASE 2

base = [1, 2, 3, 4, 5];
sample = [1, 3];

1. sort() 후 for문 실행

2. i = 0  =>  base[0] = 1, sample[0] = 1
if문 조건에 걸리므로, sample.shift() 실행
sample = [3]

i = 1  =>  base[1] = 2, sample[0] = 3

i = 2  =>  base[2] = 3, sample[0] = 3
if문 조건에 걸리므로, sample.shift() 실행
sample = []

3. for문 안의 두번째 if문 조건이 참이 되므로 바로 return ture로 함수 종료

*/