Achievement goals

멱집합 모음집 ,,
이제 혼자 풀수있을때도 됐자나..? ㅠ0ㅠ

🧐 멱집합이란?

멱살잡고싶은 집합 .. 은 아니고
주어진 집합의 모든 부분의 집합. 즉, 주어진 배열안의 요소들이 하나의 배열로 만들어질 수 있는 모든 조합의 집합체를 멱집합이라고 한다.
예를들어, [1,2,3] 에서 만들 수 있는 모든 집합(배열)은

[[공집합],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

공집합까지 포함하여 총 8개이다.

[남들 아이패드로 그릴때 손수 공책에 그려본 1인 ,, ]

잠시 포기했던 깊이우선탐색,DFS 트리구조를 떠올려본다.
왼쪽으로 가면 선택, 오른쪽으로 가면 선택x 이대로 끝까지 진행시킨다.
그림을 보면 1층에서 3층까지 총 [1,2,3] 의 배열길이만큼 깊이가 있는 것을 볼 수 있다.
이말인 즉슨, [1,2,3] 의 length 에 도달하면 출력할 수 있다.

이 구조를 바탕에 깔고 다음 문제들을 풀어보도록 하겠다.

문제 1.

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

const isSubsetOf = function (base, sample) {
};

입력
인자 1 : base // number 타입을 요소로 갖는 임의의 배열
base.length는 100 이하
인자 2 : sample //number 타입을 요소로 갖는 임의의 배열
sample.length는 100 이하
출력
boolean 타입을 리턴해야 합니다.
주의사항
base, sample 내에 중복되는 요소는 없다고 가정합니다.
시간 복잡도를 개선하여, Advanced 테스트 케이스(base, sample의 길이가 70,000 이상)를 통과해 보세요.

사실 boolean 타입을 리턴하는 문제여서
sample 에 있는 배열들을 every메소드와 그 sample 들이 base에 있는지 불리언값으로 확인해주는 includes 메소드를 사용하면 그만이지만, 이 문제에서는 시간복잡도까지 고려해야 한다.
때문에 sample.every((el)=>{return base.includes(el)}) 코드는 콘솔창에 잘 찍힘에도 테스트케이스에는 실행초과가 떠버린다.

🤔 그럼 어떻게 접근해야할까?

수도코드
1. 각 인자 배열(base,sample)을 하나씩 비교탐색하니까 순차적으로 정렬시킨다.
2. 재귀적으로 접근하기 위하여 탐색할 함수를 하나 만든다.
3. 탐색함수에서 base배열에 sample 배열요소가 있으면 해당 인덱스를 리턴하고 없으면 -1을 리턴한다.
4. 재귀적으로 돌 탐색함수식을 만든 후 종료조건을 불리언타입으로 나눈다.

🤓 풀이

const isSubsetOf = function (base, sample) {

  // 순차적으로 비교하기 위해 솔팅먼저 한다. sort : immutable 
  base.sort((a,b)=>a-b)
  sample.sort((a,b)=>a-b)

  // 재귀함수 search 만들기
  // 인자가 세개인 search : value sample 의 인덱스값, baseArr 는 base배열, start 는 다시 시작할 배열
  const search = (sampleValue, baseArr, start) => {
    //배열에 다다르게 되면 i를 리턴해버리고 그게 아니라면 -1 
    //i=0 이 되면 안되는 이유 : 재귀적으로 계속 돌아야하므로.
    for(let i = start; i < baseArr.length; i++){
      if(sampleValue === baseArr[i]){
        return i;
      }
    }
    return -1;
  }

  //재귀 search 함수를 만들었으니까 종료조건과 Recursive case 를 만든다.
  let idx = 0;
  for(let j = 0; j<sample.length; j++){
  
    //recursive case
    idx = search(sample[j],base,idx)
    
    //base case : idx 가 -1이면 false 로 종료.
    if(idx === -1){
      return false;
    }
  }
  return true;
};