두 개의 배열(base, sample)을 입력받아 sample이 base의 부분집합인지 여부를 리턴해야 합니다.
number 타입을 요소로 갖는 임의의 배열
base.length는 100 이하
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 테스트 케이스(base, sample의 길이가 70,000 이상)를 통과해 보세요.
const isSubsetOf = function (base, sample) {
let isTrue = [];
for(let i = 0; i < sample.length; i++) {
if(base.includes(sample[i])) {
isTrue.push(true);
} else {
isTrue.push(false);
}
}
for(let j = 0; j < isTrue.length; j++) {
if(isTrue[j] !== false) {
return true;
}
return false;
}
};
const isSubsetOf = function (base, sample) {
// base와 sample을 모두 오름차순으로 정리
base.sort((a, b) => a - b);
sample.sort((a, b) => a - b);
// 3개의 변수를 가진 findItem 함수 선언
// start는 base와 sample이 동시에 가지고 있는 요소가 시작되는 지점
const findItem = (item, arr, start) => {
for (let i = start; i < arr.length; i++) {
if (item === arr[i]) return i; // 같은 요소가 i번째
// arr[i]가 item 보다 커져버리면 이미 arr가 base의 교집합이 아니라는 얘기
else if (item < arr[i]) return false;
}
return false;
};
let baseIdx = 0;
for (let i = 0; i < sample.length; i++) {
baseIdx = findItem(sample[i], base, baseIdx);
if (baseIdx === false) return false;
}
return true;
};
나의 풀이는 답은 맞았지만, 시간초과로 통과하지 못했다...
findItem
함수 선언하여 base와 sample의 교집합 요소가 시작하는 지점을 start로 저장해주기 => baseIdx로 저장
arr[i]가 이미 base의 item을 벗어나는 수를 가지는 이상 sample은 더이상 base 안에 포함되지 않으므로 false 리턴
어렵다.. 나중에 꼭 다시풀기