728x90
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 이상)를 통과해 보세요.
💡 문제풀이
const isSubsetOf = function (base, sample) {
// naive solution: O(M * N)
// return sample.every((item) => base.includes(item));
// 각 배열을 정렬: O(N * logN), O(M * logM)
// N >= M 이므로, O(N * logN)
// 일단 오름차순 정렬
base.sort((a, b) => a - b);
sample.sort((a, b) => a - b);
const findItemInSortedArr = (item, arr, from) => {
for (let i = from; i < arr.length; i++) {
if (item === arr[i]) return i;
else if (item < arr[i]) return -1;
}
return -1;
};
let baseIdx = 0;
for (let i = 0; i < sample.length; i++) {
baseIdx = findItemInSortedArr(sample[i], base, baseIdx);
if (baseIdx === -1) return false;
}
return true;
};
728x90
'프로그래밍 > 알고리즘' 카테고리의 다른 글
알고리즘 문제 풀이 - largestRectangularArea, 구간트리란? (0) | 2022.07.11 |
---|---|
[알고리즘 문제 풀이] 정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다. (0) | 2022.07.03 |
[알고리즘 문제 풀이] 아래와 같이 정의된 피보나치 수열 중 n번째 항의 수를 리턴해야 합니다. (0) | 2022.07.03 |
[Javascript] 백준 10998번 알고리즘 문제 풀이 - 두 정수 A와 B를 입력받은 다음, A×B를 출력하는 프로그램을 작성하시오. (0) | 2022.06.20 |
[Javascript] 백준 1000번 알고리즘 문제 풀이 - 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. (0) | 2022.06.20 |
댓글