[23.02.24] Daily Coding 24

동화·2023년 2월 24일
0

Daily-Coding

목록 보기
14/15
post-thumbnail
  1. isSubsetOf
    두 개의 배열(base, sample)을 입력받아 sample이 base의 부분집합인지 여부를 리턴해야 합니다.
const isSubsetOf = function (base, sample) {
  return sample.every((number) => base.includes(number));
}

array 매서드인 every, inclueds사용. -> 시간 초과

시간 복잡도를 개선하기 위해 일단 배열을 오름차순으로 정렬했다.

base.sort((a, b) => a - b);
sample.sort((a, b) => a - b);
  for(let i = 0; i < base.length; i++) {
    if(base[i] === sample[0]) {
      sample.shift();
    }
  }
  if(sample.length === 0){
    return true;
  }
  return false;

그리고 base의 요소가 sample의 첫 요소와 같다면,
그 첫 요소를 제거하고 남은 요소를 반환한다 (shift()).
제거하면 이미 확인한 요소는 다시 확인하지 않을 것이므로 시간이 줄어들 것
그리고 이제 sample의 요소의 개수가 하나도 없게 되면, base에 포함된 것들이 제거된 것이므로 부분집합이라고 볼 수 있음 => true 반환

내가 쓴 답 ✍🏻

const isSubsetOf = function (base, sample) {
  base.sort();
  sample.sort();

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

레퍼런스 📌

const isSubsetOf = function (base, sample) {
  // naive solution: O(M * N)
  // return sample.every((item) => base.includes(item));

  // 각 배열을 정렬: O(N * logN), O(M * logM)
  // N >= M 이므로, O(N * logN)
  base.sort((a, b) => a - b);
  sample.sort((a, b) => a - b);

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

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

<reference>
1. base와 sample의 요소를 오름차순으로 정렬한다.
2. arr의 요소와 itemfrom 부터 비교할 함수를 만든다.

const findItemInSortedArr = (item, arr, from) => {}
  1. from 부터 arr의 길이까지 반복하는 문
    --> itemarr의 요소와 같을 경우 현재 인덱스(i)를 리턴
for (let i = from; i < arr.length; i++) {
	if (item === arr[i]) return i;
}
  1. itemarr의 요소보다 클 경우 -1을 리턴
else if (item < arr[i]) return -1;
인자 from으로 인해 작은수를 비교하지 않아도 된다.
-> 반복이 끝나도 return 되지 않았으면 -1을 리턴 (return -1)
  1. 이제 base의 요소를 반복하면서 sample의 요소를 갖고 있지 않는 반복이 있는 순간 --> 반복을 멈추고 false를 반환한다.
let baseIdx = 0;
for (let i = 0; i < sample.length; i++) {
  baseIdx = findItemInSortedArr(sample[i], base, baseIdx);
  if (baseIdx === -1) return false;
}

이 반복문이 지나도 리턴이 안됐으면 true를 리턴한다 (return true)

5개의 댓글

comment-user-thumbnail
2023년 2월 24일

레퍼런스코드 보면 이해 안가는게 정말 많앗는데 설명해주셔서 감사합니다👍

답글 달기
comment-user-thumbnail
2023년 2월 24일

레퍼런스 해설도 유용하지만, 동화님 의식의 흐름대로 풀이를 따라갈 수 있어서 좋은 거 같아요!!

답글 달기
comment-user-thumbnail
2023년 2월 25일

레퍼런스보다 동화님 코드가 더 깔쌈한디요 ~~?

답글 달기
comment-user-thumbnail
2023년 2월 26일

동화님과 레퍼런스의 큰 차이는 shift의 유무인 거 같아요! 레퍼런스는 shift 대신 for문을 써서 그나마의 시간을 더 줄인 거 같고 동화님 거는 shift를 써서 더 깔쌈한 거 같아요. 저는 동화님 방법을 택하겠습니다^^7

답글 달기
comment-user-thumbnail
2023년 2월 26일

동화님 풀이가 이해가 쏙쏙 되네용 ~!!

답글 달기