부분집합 이분탐색

lim1313·2021년 9월 4일

이분탐색

코딩테스트 & 코테 스터디

목록 보기

12/17

부분집합 여부

문제

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

입출력 예시

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

문제해결

처음 이 문제를 풀었을 때 base, sample 배열을 for문으로 하나씩 돌며 sample의 element를 모두 포함하고 있는지 확인하였다.
하지만 이렇게 풀게 되면 시간 복잡도는 O(M*N)이 된다.

1. array 메소드 사용

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

실행 시간 초과 오류 발생

2. 이중 for문

const isSubsetOf = function (base, sample) {

  base.sort((a, b) => a - b);
  sample.sort((a, b) => a - b);

  let result = true;
  for (let i = 0; i < sample.length; i++) {
    if (result === false) {
      return result;
    }
    for (let j = i; j < base.length; j++) {
      if (sample[i] === base[j]) {
        result = true;
        break;
      } else {
        result = false;
      }
    }
  }
  return result;
};

테스트는 통과했지만, 불필요한 반복이 발생하고 있다.

3. 이분탐색 ( 최종답안 )

시간 복잡도를 개선하기 위해 이전에 프로그래머스를 풀면서 학습한 이분탐색을 적용해 보았다.

const isSubsetOf = function (base, sample) {
  base.sort((a, b) => a - b);
  let arr = Array(sample.length).fill(false);

  for (let i = 0; i < sample.length; i++) {
    let max = base.length - 1;
    let min = 0;

    while (min <= max) {
      let midIdx = Math.floor((max + min) / 2);

      if (base[midIdx] === sample[i]) {
        arr[i] = true;
        break;
      }

      if (sample[i] >= base[midIdx]) {
        min = midIdx + 1;
      } else {
        max = midIdx - 1;
      }
    }
  }
  return !arr.includes(false);
};

우선 base를 sort로 정렬하여 이분탐색 조건을 만족시킨다.
sample는 하나씩 요소가 있는지 확인해야 하기 때문에, 반복문을 사용한다.
base의 인덱스를 절반씩 줄여나가기 위해, max, min의 변수에 가장 작은 인덱스, 가장 큰 인덱스를 할당한다.
base의 요소의 중간값과 sample[i]의 크기를 비교하며 base의 중간값요소가 큰 경우 중간값 인덱스의 + 1, 작은 경우 중간값 인덱스의 - 1을 각각 min, max에 재할당한다.
이 과정을 반복하여 base의 중간값요소와 sample[i]의 요소가 같다면, 새로 생성해 두었던 arr 배열에 true를 할당한다.
while의 조건인 min <= max가 false가 되면 arr의 element값을 변경하지 못한채 while문이 종료된다.
최종적으로 arr에 false가 없다면 모두 포함된 값이 된다.

위의 코드는 중간값과의 크기비교를 통해 필요한 탐색 횟수를 줄여주어 시간 복잡도를 개선시킨다.

reference

const isSubsetOf = function (base, sample) {
  base.sort((a, b) => a - b);
  sample.sort((a, b) => a - b);

  let result = true;
  for (let i = 0; i < sample.length; i++) {
    if (result === false) {
      return result;
    }
    for (let j = i; j < base.length; j++) {
      if (sample[i] === base[j]) {
        result = true;
        break;
      } else {
        result = false;
      }
    }
  }
  return result;
};

해당 문제의 최종적인 의도는 불필요한 반복을 제거하는 것이다.

이를 위해서 sample의 요소를 찾은 인덱스를 저장하고, 다음 요소를 찾을 때에는 찾은 인덱스 이후의 인덱스만 탐색하면 되기 때문에, 불필요한 반복이 줄어들게 된다.