isSubsetOf 문제풀이

문제:

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

 

 

입력:

인자1 : base	인자1 : sample
number 타입을 요소로 갖는 임의의 배열 base.length는 100 이하	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 이상)를 통과해 보세요.

 

📝 이 문제는... 

이 문제는 for문으로 includes를 확인하면 간단하게 끝나는 것 같지만,

시간제한이 걸려있어 최적화를 시키지 않으면 통과가 되지 않는다.

이때 두 배열을 오름차순으로 먼저 재정렬하고, 

이미 체크한 부분은 건너뛰는 식으로 시간복잡도를 개선한다.

 

 

---

첫번째 풀이: 기본 풀이법

const isSubsetOf = function (base, sample) {
  return sample.every((item) => base.includes(item));
};

 

위 코드는 시간복잡도가 크다. 

그 이유를 하나씩 생각해보자.

 

첫번째 코드를 사용할때 아래와 같이 입력한다면

 

let base = [1, 2, 10, 99, 123, 7];
let sample = [123, 99, 10, 8, 9];
isSubsetOf(base, sample);

 

1. 일단 첫번째 sample[0]인 123이 먼저 base에 해당하는지 하나하나 비교한다. 

base[0],base[1],base[2]base[3]은 모두 123이 아닌것을 차례대로 체크하고, base[4]에 이르러서야 123이 있다고 판명하고,includes(sample[0])은 true로 다음턴으로 넘어간다.

 

2. 그럼, 이번엔 sample[1]인 99를 갖고 base와 비교한다.

base[0],base[1],base[2]은 모두 99가 아닌것을 차례대로 체크하고, base[3]에 이르러서야 99가 있다고 판명한다. 역시 true로 다음턴으로 넘어간다.

 

3. 이번엔 sample[2]인 10을 갖고 base와 비교한다.

base[0],base[1]은 모두 10이 아닌것을 차례대로 체크하고, base[2]에 이르러서야 10이 있다고 판명한다. 역시 true로 다음턴으로 넘어간다.

 

4. 이번엔 sample[8]인 8을 갖고 base와 비교한다.

base[0],base[1],base[2],base[3],base[4],base[5] 모두 차례를 돌리면서 8이 없다는 것을 판명하고 false가 되어 결과적으로 every가  false로 종료된다.

 

이 과정을 보면 한 아이템마다 불필요한 반복이 계속 반복되고 있다. 총 15번의 비교 연산이 반복되었다. 

4개의 아이템을 체크하는데 15번. 

만약 base와 sample의 길이가 70,000이상으로 길어진다면???? 연산은 말도 못하게 많아질 것이다.

 

이 반복적인 연산을 어떻게하면 고칠 수 있을까?

 

 

 

아이디어 생각해보기

두번째 풀이를 보기 전에 한번 생각해보자.

 

let base = [6,3,1,5,2,4];
let sample = [4,5];
isSubsetOf(base, sample);

 

위와 같은 경우에 만약 아래와 같이 오름 차순으로 정리한다면?

 

base = [1,2,3,4,5,6];
sample = [4,5];

 

이렇게 둘 다 오름차순으로 정리한다면

sample[0]인 4를 체크하기 위해 base[0],base[1],base[2],base[3]까지 돌았다면 

sample[1]인 5를 체크하기 위해 또 base[0]부터 돌아야 할까?

 

우리는 이미 sample[0]을 체크했기 때문에

sample[1]과 동일한 값이 있어도 base[3]이후에 있을 것이란 것을 안다.

 

왜냐 sample[0]===base[4]이고, 

sample과 base는 모두 오름차순으로 정리되었기 때문에,

sample[1]은 base[4]이후 index에 들어가 있을 테니까.

 

그렇다면 우린 쓸데없이 base[0]~base[3]을 체크하지 않고, base[4]부터 체크를 하면 된다.

 

바로 이 두 포인트가 중요하다.

📌최적화 POINT 두가지: 

1. 오름차순으로 정리하기
2. 체크를 완료한 아이템의 index를 기억해서 다음 체크 때 그 index 이후를 체크하기

 

 

두번째 풀이: 시간 복잡도 개선 풀이법

const isSubsetOf = function (base, sample) {
  base.sort((a, b) => a - b); //1️⃣ 오름차순으로 정리
  sample.sort((a, b) => a - b);//1️⃣ 오름차순으로 정리
  
  const findItemInSortedArr = (item, arr, from) => { 
  	// 2️⃣ 찾을 sample[i]아이템과, 그 아이템이 있는지 찾을 arr인 base, 그리고,
    //어디에서 부터 index를 찾으면 좋을지를 받아서 
    //arr에 item이 있는지 from 인덱스부터 체크한다.
    for (let i = from; i < arr.length; i++) {
      if (item === arr[i]) return i;//3️⃣ 만약 있다면 base에 그 아이템의 index를 리턴한다.
      else if (item < arr[i]) return -1; 
      //3️⃣ 동일한 아이템이 안나왔는데, 그 아이템보다 큰 숫자가 나오면 오름차순의 특성상 이후에도 아이템은 없다.
      //이땐 -1을 리턴한다.
    }
    return -1; //4️⃣ 다 돌았는데도 아무것도 return이 안되는 경우는
    //sample의 아이템이 base의 가장 큰 아이템보다도 큰 경우이다.
    //이때도 base에 없는 것이므로 -1을 리턴한다.
  };

  let baseIdx = 0; //일단 처음 sample[0]찾을 땐 base[0]부터 찾아야한다.
  for (let i = 0; i < sample.length; i++) {
    baseIdx = findItemInSortedArr(sample[i], base, baseIdx);
    //5️⃣ 아이템이 있다면 그 아이템의 index가 리턴되고 그 숫자가 baseIdx가 되어 다음 for 턴으로 넘어간다.
    if (baseIdx === -1) return false;
    //6️⃣ 아이템이 없다면 -1이 리턴될테고 더이상 찾을 필요도 없이 false를 리턴한다.
  }
  return true; //7️⃣ sample을 다돌았는데도 false로 리턴되지 않않으니, 이제 true로 마감한다.
};

 

첫번째 풀이보다 코드는 길고 복잡하지만, 성능면에서 훨씬 우세하다. 

주석이 있어 복잡해 보이니 깔끔하게 정리된 코드도 추가한다.

 

const isSubsetOf = function (base, sample) {
  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;
};

 

이 아이디어가 얼마나 멋진지 알아보기 위해 동일한 경우에 얼마나 최적화가 되는지 테스트해 보겠다.

아래의 첫번째 풀이의 같은 예시를 도출하기 위해 이번엔 몇번을 순회해야 할까

 

let base = [1, 2, 10, 99, 123, 7];
let sample = [123, 99, 10, 8, 9];
isSubsetOf(base, sample);

 

1. base=[1,2,7,10,99,123], sample=[8,9,10,99,123]으로 정리된다.

 

2. base[0],base[1],basae[2]까지 돌았는데 sample[0]인 8과 동일한 숫자가 없었다. 그런데  8 < base[3](=10)이므로 base에는 더이상 8이 없을 것이란 것을 안다. false로 리턴한다.

 

15번 순회 후 찾을 수 있던 결과가 단 3번으로 도출되었다. 

만약 배열이 더 길어진다면? 이 차이는 큰 힘을 발휘할 것이다.

 

 

 

---

이 풀이 아이디어는 사실 검색과 reference코드를 통해 알게되었는데 정말 이마를 탁치는 아이디어였다! 

알고리즘 공부는 참 열받지만 재밌는 것 같다.