알고리즘: 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 이상)를 통과해 보세요.

풀이 (of mine)

1. sample의 요소가 다 base에 있는지 for문을 돌려서 확인 -> includes ?
2. 모든 답이 다 true가 나왔을 경우에만 true를 리턴
3. 아닌 경우 false 리턴

const isSubsetOf = function (base, sample) {
  let isTrue = [];
  for(let i = 0; i < sample.length; i++) {
    if(base.includes(sample[i])) {
      isTrue.push(true);
    } else {
      isTrue.push(false);
    }
  } 

  for(let j = 0; j < isTrue.length; j++) {
    if(isTrue[j] !== false) {
      return true;
    }
    return false;
  }
};

레퍼런스 풀이

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

  // 3개의 변수를 가진 findItem 함수 선언
  // start는 base와 sample이 동시에 가지고 있는 요소가 시작되는 지점
  const findItem = (item, arr, start) => {
    for (let i = start; i < arr.length; i++) {
      if (item === arr[i]) return i; // 같은 요소가 i번째
      // arr[i]가 item 보다 커져버리면 이미 arr가 base의 교집합이 아니라는 얘기
      else if (item < arr[i]) return false;
    }
    return false;
  };

  let baseIdx = 0;
  for (let i = 0; i < sample.length; i++) {
    baseIdx = findItem(sample[i], base, baseIdx);
    if (baseIdx === false) return false;
  }
  return true;
};

한 줄 평

• 나의 풀이는 답은 맞았지만, 시간초과로 통과하지 못했다...

• findItem 함수 선언하여 base와 sample의 교집합 요소가 시작하는 지점을 start로 저장해주기 => baseIdx로 저장

• arr[i]가 이미 base의 item을 벗어나는 수를 가지는 이상 sample은 더이상 base 안에 포함되지 않으므로 false 리턴

• 어렵다.. 나중에 꼭 다시풀기