[자료구조/알고리즘] 211012 두개의 배열 부분집합여부 #set메서드

📌 두개의 배열 부분집합 여부확인

이렇게만 보고서는 문제이해가 어려울 수 있다. 아래 예시를 보도록 한다. 주어지는 인자 값은 sample 그리고 base라는 이름의 배열이다. 그리고 base는 number 타입을 요소로 갖는 임의의 배열이며 base.length는 100 이하이다. sample은 number 타입을 요소로 갖는 임의의 배열 이며 sample.length는 100 이하이다.

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

이 문제를 보는 순간 '오 이건 쉬운거 아닌가' 라고 생각했다. 보자마자 드는 게 바로 '이중 반복문을 돌려서 각각의 인덱스 값 비교해주면 될 것 같은데'였다. 그래서 신나게(?) 이중반복문을 돌렸다.
결과는 테스트케이스 7개중 5개 통과 2개 실패...😥

이 문제가 원하는 건, 시간복잡도를 개선하라는 것이었다. 이중반복문을 돌리면 sample과 base의 길이가 굉장히 길 때는 (길이가 100개일수도 있으니까) 비효율적이고 느려질 가능성이 높다. 하지만 처음에 나는 내가 만들어두었던 코드에서 변경할 수 있지 않을까 싶어서 아고라 스테이츠에 문의를 넣어보았다. 하지만 그 코드에선 도저히 해결이 불가능하다는 답변을 정성스럽게 해주셧다. (비꼬는 거 아닙니다ㅠㅠ 너무나 감사합니다ㅠㅠ 이름모를 은인분ㅠㅠ)

☑ 처음 내가 쓴 코드

const isSubsetOf = function (base, sample) {
  // TODO: 여기에 코드를 작성합니다.
  // 1) 처음 나의 접근
  for(let i=0; i<base.length; i++) {
    for(let j=0; j<sample.length; j++) {
      if(base[i] === sample[j]) {
        return true 
      }
        return false
    }
  }
}  

☑ 보조함수 생성 및 이용

레퍼런스코드는 일단 base와 sample을 sort를 이용하여 정렬하는데 오름차순으로 정렬한다. 이름모를 은인 분의 말로는 sort알고리즘으로 선형검색을 시도하되 연산수를 줄인것이라고 했다. JS에서 사용하는 sort 알고리즘은 시간복잡도가 O(n log n) 으로 상당히 효율적이라고 했다.(나중에 시간복잡도에 대해서도 따로 공부해서 정리해야 할듯하다.)

보조 함수조차도 이해하기 어려웠어서 많이 헤맸었다. 함수가 호출되는 순간에 그 함수를 뛰어넘고 다음 변수로 넘어가는걸 디버거로 확인했다.

토이3번문제 문의

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;
};

☑ Set 메서드 이용

Set 메서드를 이용해서 푸는 방법이 존재했다.

Set메서드 MDN

이렇게 배열을 객체화 시켜주는 동시에 여러 메소드가 내장되어있었다. set메서드에 요렇게 내장되어있는 has로 풀었던 분이 계셨다.
그래서 이렇게도 테스트케이스를 통과하는게 신기했다. (왜 통과하는지는 아고라스테이츠에 문의해봐야 할 것 같다)

let newBase = new Set(base)
let count = 0;

이 두개의 변수를 가지고 sample 배열을 조회하는 동안에 만약 newBase가 sample[i]값을 가지고 있다면 count 를 1씩 늘린다. 그리고 count가 sample의 길이와 같다면 return true하고 아니라면 return false를 해준다.

☑ shift 메서드 이용

구글링을 해봤는데 이해하기도 쉽고 시간복잡도도 통과하는 코드였다. base요소와 sample의 요소가 일치하면 sample의 요소를 삭제하게 진행하였고, sample의 길이가 최종적으로 0 이 되면 true 리턴한다.

const isSubsetOf = function (base, sample) {
  // TODO: 여기에 코드를 작성합니다.
  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;
};