isSubsetOf

문제

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

입력

인자 1 : base

number 타입을 요소로 갖는 임의의 배열
base.length는 100 이하

인자 2 : sample

number 타입을 요소로 갖는 임의의 배열
sample.length는 100 이하

출력

boolean 타입을 리턴해야 합니다.

주의사항

base, sample 내에 중복되는 요소는 없다고 가정합니다.

입출력 예시

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 이상)를 통과해 보세요.

첫번째. count를 사용하여 시간복잡도를 개선한다. includes를 사용하면 불필요하게 너무 많이 돌게된다. 이런 불필요한 작업을 개선하는것이다.

const isSubsetOf = function (base, sample) {
  // TODO: 여기에 코드를 작성합니다.
  let count = 0
  for(let i=0; i<base.length; i++){
    for(let j=0; j<sample.length; j++){
      if(base[i] === sample[j]){
        count ++
        break;
      }
    }
  }
  if(sample.length === count){
    return true
  }
  return false;
};

1. 카운트라는 변수를 만들어준다.

2. 반복문을 순회하다가 만약 base[i] === sample[j] 이면 카운트를 증가해주고, 브레이크.스탑. <= 뒤에를 더이상 볼필요가없다.

예를들어 base[0] = 1 , sampe[0] = 1 sample[1] = 3 이였다. i=0일때 j =1값을 생각해야할 이유가있나? 이미 같은데

그렇기에 break를 걸고 i=2로 뛰어넘는다.

3. 부분집합이려면 sample의 모든 요소를 다 가지고있어야한다. 카운트값이 길이와 같으면 전부 포함이므로 true 아니면 false

const isSubsetOf = function (base, sample) {
  // TODO: 여기에 코드를 작성합니다.
  base.sort();
  sample.sort();
  for(let i=0; i<base.length; i++){
    if(base[i] === sample[0]){
      sample.shift()
    }
 }
 if(sample.length === 0){
   return true
 }
 return false; 
};

base, sample을 순서대로정렬해준다.

비슷한값을 먼저 찾기위해서는 이작업이 필수다.

12345 , 12

34152 , 21

이 둘의차이를 생각해보자. 정렬을 해주지않으면 시간복잡도가 올라간다. 시간복잡도 개선을 해주기위해서 sort를 쓴다.