Section3 Daily Coding 24

• 두 개의 배열(base, sample)을 입력받아 sample이 base의 부분집합인지 여부를 리턴해야 합니다.
• 시간 복잡도를 개선하여, Advanced 테스트 케이스(base, sample의 길이가 70,000 이상)를 통과해 보세요.

✅ 인자 1 : base

• number 타입을 요소로 갖는 임의의 배열
• base.length는 100 이하

✅ 인자 2 : sample

• number 타입을 요소로 갖는 임의의 배열
• sample.length는 100 이하

📖 입출력 예시

let base = [1, 2, 3, 4, 5];
let sample = [1, 3];
let output = isSubsetOf(base, sample);
console.log(output); // --> true

❌ 처음 접근 방식

//각 요소가 배열에 속해있는지 확인, 기존 배열의 길이와 같은 지 리턴
const isSubsetOf = function (base, sample) {
  // TODO: 여기에 코드를 작성합니다.
  return sample.filter((el) => base.includes(el)).length === sample.length;
};

❌ 시간 복잡도가 0(M*N) 다른 풀이

비슷한 풀이이지만 Array.prototype.every() 활용

//sample의 모든 요소가 base의 포함 되어 있는 지 체크 후 boolean return
const isSubsetOf = function (base, sample) {
  // TODO: 여기에 코드를 작성합니다.
  return sample.every((item) => base.includes(item));
};

✅ 시간 복잡도를 고려한 나의 풀이

• 한번 탐색한 곳은 다시 탐색하지 않는 아이디어

const isSubsetOf = function (base, sample) {
  //오름차순 정렬하여 작은 수 부터 비교
  base.sort((a, b) => a - b);
  sample.sort((a, b) => a - b);
  //두 배열 모두 오름차순 정렬 시 중복 검사가 필요 없어 인덱스 저장 변수 선언
  let checkedIndex = 0;
  // 정답을 리턴 할 변수(true로 시작)
  let answer = true;

  //sample 내부 요소 반복
  for (let i = 0; i < sample.length; i++) {
    //탈출 케이스
    if (!answer) break;
    // base 내부 요소 반복(이미 탐색한 index는 checkedIndex로 피해간다. 
    for (let j = checkedIndex; j < base.length; j++) {
      //sampe의 요소가 base에 존재한다면
      if (sample[i] === base[j]) {
        //탐색한 요소를 재 탐색하지 않기 위해 탐색한 index 저장
        checkedIndex = j;
        break;
      }
      //여기서 부터는 정답이 아닌 경우
      //1번째 sampe의 값보다 base의 값이 큰 경우
      if (sample[i] < base[j]) {
        answer = false;
        break;
      }
      //마지막까지 탐색하였는데 sample의 값이 base에 없던 경우
      if (j === base.length - 1 && sample[j] !== sample[i]) {
        answer = false;
        break;
      }
    }
  }
  return answer ? true : false;
};

✅ 시간 복잡도를 고려한 레퍼런스 풀이

각 배열을 정렬: O(N logN), O(M logM)
N >= M 이므로, O(N * logN)

const isSubsetOf = function (base, sample) {
  // 각 배열을 정렬: O(N * logN), O(M * logM)
  // N >= M 이므로, O(N * logN)
  base.sort((a, b) => a - b);
  sample.sort((a, b) => a - b);

  //item: sample의 요소
  //arr: 정렬한 base 배열
  //from: 이미 탐색한 index
  const findItemInSortedArr = (item, arr, from) => {
    //중복 탐색을 하지 않게 i값에 from
    for (let i = from; i < arr.length; i++) {
      //sample의 요소가 from에 있다면 return index
      if (item === arr[i]) return i;
      //없다면 -1
      else if (item < arr[i]) return -1;
    }
    //탐색 종료 시에도 -1
    return -1;
  };

  // baseIdx 설정(탐색한 요소 다시 탐색)
  let baseIdx = 0;
  //sample의 요소 반복
  for (let i = 0; i < sample.length; i++) {
    //요소에 대하여 findItemInSortedArr 실행
    baseIdx = findItemInSortedArr(sample[i], base, baseIdx);
    //-1을 받으면 false로 종료(하나의 요소라도 없으면 false)
    if (baseIdx === -1) return false;
  }
  //탐색이 잘 끝났다면 성공
  return true;
};

🔑 Set을 사용하여 시간 복잡도 줄이기

✅ Set.has VS Array.includes() 시간복잡도

• Set.has : O(1)
• Array.includes() : O(n)
  Set.has를 사용하여 시간 복잡도를 줄였다.

const isSubsetOf = function (base, sample) {
  //set 시간 복잡도 1 배열 n
  let setBase = new Set(base);
  for (let el of sample) {
    if (!setBase.has(el)) return false;
  }
  return true;
};

🔑 번외 Set 사용하여 편하게 풀기

Set을 사용하여 배열을 합친 후 길이로 부분 집합 여부 판단.

• 배열로 리턴 시 length
• set 사용 시 size

const isSubsetOf = function (base, sample) {
   const sSet = [...new Set([...base, ...sample])];
  return base.length === sSet.length

  const sSet2 = new Set([...sample, ...base]);
  return (base.length === sSet2.size)
};

---

📖 추가 학습

• Array.prototype.every() : every() 메서드는 배열 안의 모든 요소가 주어진 판별 함수를 통과하는지 테스트. Boolean 값을 반환

ex) 배열의 모든 요소가 10보다 더 큰지 테스트

function isBigEnough(element, index, array) {
  return element >= 10;
}
[12, 5, 8, 130, 44].every(isBigEnough);   // false
[12, 54, 18, 130, 44].every(isBigEnough); // true

• Set.prototype.size : size 접근자 속성은 Set 객체의 원소 수를 반환합니다.

const set1 = new Set();
const banana = "banana";

set1.add(42);
set1.add('forty two');
set1.add('forty two');
set1.add(banana);

console.log(set1) //Set(3) {42, 'forty two', 'banana'}
console.log(set1.size); //3