알고리즘 4 : 부분집합인지 검사하기

문제 :

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

입력 :

• base : - number 타입을 요소로 갖는 배열, base.length는 100 이하
• sample : - number타입을 요소로 갖는 배열, sample.length는 100이하

출력 :

boolean 타입 리턴

주의사항 :

base, sample내 중복되는 요소는 없다

시간복잡도를 개선하여 base,sample의 길이가 70,000 이상일 때에도 정상적으로 작동할 수 있게 하자.

입출력 예시

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

코드

const isSubsetOf = function (base, sample) {

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

  function func(samp,base,from){
    for(let i = from;i<base.length;i++){
      if(samp===base[i]) return i
      else if(samp<base[i])return -1
    }
    return -1
  }

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

상세설명

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

위와 같은 상황에서 sample[0]=1을 base의 모든 요소랑 비교한 후, sample[1]=3을 base의 모든 요소랑 비교할 것이다.

• 배열을 오름차순으로 정렬한다.

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

• sample의 요소를 차례대로 base의 모든 요소랑 비교할 것.

let idx = 0;
 for(let i = 0;i<sample.length;i++){//sample의 요소에 차례대로 적용한다.
   idx = func(sample[i],base,idx)
   if(idx===-1)return false
 }


  function func(samp,base,from){
    for(let i = from;i<base.length;i++){
      if(samp===base[i]) return i       //samp가 base의 어떤 요소랑 같을 때 그 인덱스를 반환한다.
      else if(samp<base[i])return -1   //samp가 base보다 큰 경우에는 같을 확률이 없으므로 빠져나온다
      //불필요한 작업을 생략함으로써 시간복잡도를 개선한다.
    }
    return -1
  }