부분집합 확인 Javascript

cptkuk91·2022년 8월 6일
1

Algorithm

목록 보기
47/161
post-custom-banner

부분집합인지 확인하는 문제

두 개의 배열(base, sample)을 입력받아 sample이 base의 부분집합인지 여부를 반환하라.

for문을 통해 문제를 해결하려한다면 시간복잡도를 고려하지 않았기 때문에, 다른 방법으로 접근해야한다.

우선 sample이 base의 부분집합인지 확인을 하는 문제이기 때문에 2개의 배열 모두 정렬시킨다.
이후 base를 탐색할 때 특정범위만 탐색해야한다.

일치하는 인덱스값을 저장 후 요소를 탐색할 때 저장된 값을 사용해 문제를 해결하자.

// subsetOf는 부분집합을 뜻한다.
function solution(base, sample) {
  base.sort((a, b) => a - b);
  sample.sort((a, b) => a - b);

  const checkArr = (find, compare, from) => {
    for (let i = from; i < compare.length; i++) {
      if (find === compare[i]) {
        return i;
      } else if (find < compare[i]) {
        return -1;
      }
    }
    return -1;
  };

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

profile
메일은 매일 확인하고 있습니다. 궁금하신 부분이나 틀린 부분에 대한 지적사항이 있으시다면 언제든 편하게 연락 부탁드려요 :)
post-custom-banner

0개의 댓글