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

풀이

// 포함이 되어 있는지 여부만 확인 시 
// every, includes 를 사용해서 구할 수 있다. 
const isSubsetOf = (base, simple) => {
	let result = simple.every(el => base.includes(el));
	return result
}

하지만, 위의 풀이는 모든 수를 비교 하기 때문에 시간 복잡도가 높다. O(base*simple)

그래서 단순한 비교에 사용하는게 좋다.  시간을 단축하기 위해서는  O(base * log sinple)의 형태로 

비교횟수를 줄여야 한다.

// base, simple 가 정렬 되어 있다고 가정 후 진행 
// 정렬되지 않은 배열일 경울 sort 를 이용해서 정렬이 필욜함

const isSubsetOf = (base, simple) => {
	
    const find = (el, arr, middle) => { // 시작값은 처음으로 일치한 수, 초기값은 0
    	for(let i = middle; i < arr.length; i++){
        	if(el === arr[i]){
            	return i;
            }
            else if(el < arr[i]){
            	return -1;
            }
        }
        return -1;
    }
    
    let sameNum = 0; // 같은 수가 나오면 같은 수보다 작은수를 다 제외한다. 초기값은 0
    
  	for (let i = 0; i < sample.length; i++) {
   		sameNum = find(sample[i], base, sameNum);
		if (sameNum === -1) { // -1이 나온다면 무조건 false
			return false;
		}    
  	}
  	return true;
}

point 

· 비교 값이 크지 않을 때는 메소드를 활용하여 확인 할 수 있어야 한다(공간 복잡도)

· 비교 값이 커질 수록 비교 대상(base)를 줄여가면서 검색 할 수 있야 한다.(시간 복잡도)