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 이상)를 통과해 보세요.
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
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;
};
|
cs |
배운점
1. 배열의 every method를 적절히 사용하자. callback 함수의 결과가 모두 true 일때만 true를 반환하고, 아니면 false를 반환한다.
2. N, M개의 원소를 갖는 배열들을 모두 검사하는 알고리즘의 시간복잡도는 O(N * M) 이다.
sort의 기본적인 시간복잡도는 N * logN 이다.
3. 정렬을 하면 시간복잡도를 N * logN 으로 줄일 수 있고, 순서대로 크기를 비교하는 논리를 적용할 수 있으므로 각 원소들의 크기, index를 활용할 수 있게 된다.
728x90
반응형
'Computer Science > Algorithm' 카테고리의 다른 글
Prm 6 : Sudoku / parseInt, [...Array().keys()].slice() (0) | 2021.01.01 |
---|---|
BubbleSort (0) | 2020.12.29 |
Prm 2 : fibonacci (0) | 2020.12.27 |
Prm 1 : permutation (0) | 2020.12.25 |
[프로그래머스] [Lv. 1](matrix)카카오 크레인 인형뽑기 게임 (0) | 2020.12.22 |