알고리즘 문제풀이 03 - isSubsetOf

문제

두 개의 배열(base, sample)을 입력받아 sample이 base의 부분집합인지 여부를 리턴해야 합니다.

입출력 예시

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) {
  for(let i = 0; i < sample.length; i++) {
    if(base.indexOf(sample[i]) === -1) {
      return false;
    }
  }
  return true;
}

1. indexOf 메소드를 이용해 base에서 sample요소 각각의 index를 찾는다.
2. 값이 하나라도 -1이 되면 sample은 base의 부분집합이 아니므로 false를 리턴, 모두 순회한 뒤 -1이 없다면 true를 리턴한다.

🧐 문제점

sample의 요소 각각을 확인하기 위해 매번 base 전체를 순회한다.

시간복잡도

O(N^2)

---

해결방법

const isSubsetOf = function (base, sample) {
  //base, sample을 오름차순으로 정렬
  base.sort((a, b) => a - b);
  sample.sort((a, b) => a - b);

  //base를 순회하면서 sample[i]의 index를 찾는 함수
  const findItemInSortedArr = (item, arr, from) => {
    for (let i = from; i < arr.length; i++) {
      //sample[i]와 같은 요소를 찾으면 index 리턴
      if (item === arr[i]) {
        return i;
      /*오름차순 정렬이므로 sample[i]보다 base의 요소가 크면
      더이상 순회하지 않고 -1리턴.*/
      } else if (item < arr[i]) {
        return -1;
      }
    }
    //sample[i]가 없으면 -1리턴.
    return -1;
  };

  let baseIdx = 0;
  for (let i = 0; i < sample.length; i++) {
    // findItemInSortedArr의 리턴값 index부터 순회 시작
    baseIdx = findItemInSortedArr(sample[i], base, baseIdx);
    //리턴값이 -1이면 부분집합이 아니기 때문에 false 리턴
    if (baseIdx === -1) return false;
  }
  // 모두 순회 후 -1이 없다면 true 리턴
  return true;
};

시간복잡도

O(N)
각 배열을 정렬
O(logN)
findItemInSortedArr의 리턴값 index부터 순회를 하기 때문에
연산이 진행될 때마다 탐색해야할 요소가 줄어듦

→ O(N * logN)