문제 : 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 : 시간 복잡도를 개선하여, Advanced 테스트 케이스(base, sample의 길이가 70,000 이상)를 통과해 보세요.

문제의 접근

처음 이 문제를 보자마자 든 생각은 매우 간단하다 생각했다. 부분집합인지 아닌지 간단한 논리다. sample에 있는 순자 중 하나라도 base에 들어 있지 않으면 false를 리턴 하면 된는 것이다.

const isSubsetOf = function (base, sample) {
  // TODO: 여기에 코드를 작성합니다.
  for(let i = 0; i < sample.length; i++){
    if(!base.includes(sample[i])){
      return false;
    }
  }
  return true;
};

다음 코드는 sample의 인자를 하나 씩 꺼내와서 base에 있는지 여부를 확인해서 포함 되어 있지 않으면 바로 false를 리턴하고 모든 for문을 무사히 통과하면 true를 리턴하는 식이다.

Advanced

콘솔창에 실행 시켜보면 모두 잘 출력 되고 있다 하지만... 테스트를 돌려본다면 실행시간이 초과된다고 나오고 있다. 그렇다면... 결국 이 문제도 Advanced를 한번에 해결해야 하는 것이다.

지금 사용한 코드는 O(n)의 복잡도를 가진다. 복잡도로 치면 3번째로 효율적인 시간복잡도를 가지는데 이보다 더 효율적인 복잡도를 써야한다는 것이다. 그렇다면 O(logn) 혹은 O(1)의 복잡도를 가져야 한다. 당연히 이 문제는 O(1)의 복잡도로는 해결할 수 없다. 그렇다면 자연스레 O(logn)의 복잡도를 가질 수 밖에 없는 것이다. 즉, 이 문제는 이분 탐색법 (Binary Search)을 이용해서 문제를 해결해야 한다고 생각 된다.

이전 페어분과 대화를 통해서 처음 코드가 왜 시간초과가 나오는지 알았다. 바로 includes함수 때문이다. 이 함수는 그 배열의 모든 값을 확인하기 때문에 O(n)의 복잡도를 가지고 있던 것이다. 그렇다면 내 첫 함수는 O(n)의 복잡도가 아닌 O(n^2)의 복잡도를 가지고 있던 것이다. 그렇다면 간단하게 includes를 대신해서 sample의 값이 base에 있는지만 확인해주면 간단한 일이다.

const isSubsetOf = function (base, sample) {
  // TODO: 여기에 코드를 작성합니다.
  base.sort();
  sample.sort();
  for(let i = 0; i < base.length; i++) {
    if(base[i] === sample[0]) {
      let num = sample.shift();
    }
  }
  if(sample.length === 0){
    return true;
  }
  return false;
};

위 코드는 includes를 대신해서 값의 포함 여부를 확인해 주는 것이다. 더 효율적인 탐색을 위해 먼저 sort()함수를 통해 정렬을 해준 뒤 값을 하나하나 비교해보고 값이 있다면 그 값을 제거해주는 것이다. 그렇게 만약 sample에 모든 값이 없어진다면 부분집합이 성립하는 것이다. 하지만 그렇지 않다면 부분집합이 아니라는 것이다.

문제를 통해 생각해 볼 것

시간 복잡도를 생각하는데 있어서 내가 사용하는 함수를 고려하지 않아서 문제를 너무 어렵게 생각했다. 만약 저 문제를 이분 탐색법으로 찾으려 했다면 매우 오랜 시간을 고민했을 것이다. 문제를 쉽게 접근하는 것은 좋지만 내가 쓰는 도구가 어떤 건지도 확실히 알 필요가 있다.
그래도 문제를 생각할 때 시간복잡도를 고려할 수 있게된 건 매우 좋은 발전이다. 앞으로도 더 효율적인 알고리즘을 찾을 수 있는 좋은 발판이 될 것 같다.