문제

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

입력

• 인자 base
  number 타입을 요소로 갖는 임의의 배열
  base.length는 100 이하
• 인자 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 이상)를 통과해 보세요.

---

접근방식

시간 복잡도를 생각하지 않고, 짰던 처음 로직은 아주 심플했다.
sample 배열의 요소가 base 배열에 포함되어 있는지 여부만을 고려하면 되기 때문에 sample 배열의 요소를 순회하며 요소가 base 배열에 몇 번째 요소인지 indexOf()를 써서 찾는다.
만약, sample 요소가 하나라도 base 배열에 포함되지 않는다면 바로 리턴 fasle를 하면되고, 요소를 모두 포함하고 있으면 true로 리턴하면 된다.

위 수도코드를 토대로 작성하였더니 역시나 실행초과가 뜬다ㅠ

처음 제출 코드

const isSubsetOf = function (base, sample) {
 for(let i=0; i<sample.length; i++) {
    if(base.indexOf(sample[i]) === -1) return false;
 }
 return true;
}

indexOf도 base배열을 반복문과 같이 순회하는 메서드이므로 이중 for문으로 시간 복잡도는 O(n2)인데 시간 복잡도를 개선할 수 있는 로직으로 접근해야했다.

base 배열에서 sample 요소가 포함된 인덱스를 제거하고 다음 요소들을 찾아주면 base 배열 순회 범위가 줄어들어 시간 복잡도도 개선될 것 같았다.
그런데 문제는 로직을 어떻게 짜느냐..ㅎ

결국 고민하다 시간 내 짜지 못하고 레퍼 코드를 봤다. 아래는 레퍼 코드를 이해한 내용을 주석으로 달아보았다.
indexOf를 대체할 로직을 함수로 빼서 탐색 범위를 줄이도록 만들어 준게 이번 문제의 핵심이었다.

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

  //sample 요소 base 배열에 포함 여부 검사하는 함수 
  //item 인자: sample[i] 
  //arr 인자: base 배열
  //from 인자: 0 || sample[i]가 포함된 인덱스 
  const findItemInSortedArr = (item, arr, from) => {
    //sample[i]가 포함된 인덱스부터 순회를 시작한다. >> 탐색 범위 축소
    for (let i = from; i < arr.length; i++) {
      //sample[i]가 포함된 인덱스를 baseIdx에 재할당 
      if (item === arr[i]) return i;
      //오름차순 정렬했기 때문에 
      //base[i]가 sample[i] 보다 더 큰 경우는 
      //base 배열에 포함되지 않으니 -1을 리턴 
      //>> 탐색 범위 축소(배열의 길이만큼 다 돌지 않아도 된다.)
      else if (item < arr[i]) return -1;
    }
    //base 배열을 다 돌아도 인덱스를 찾지 못했다면 -1을 리턴
    return -1;
  };

  let baseIdx = 0;
  //sample 배열을 순회한다.
  for (let i = 0; i < sample.length; i++) {
    baseIdx = findItemInSortedArr(sample[i], base, baseIdx);
    if (baseIdx === -1) return false;
  }
  return true;
}