Algorithm problem-03

1. 문제

• 두개의 배열을 받아 작은게 큰것의 부분집합 인지를 검사
• 배열은 중복 요소가 없는 상태
• 배열은 100 이하의 길이를 가짐

2. 시도

• 각 배열을 오름차순 sort한 후 겹치는 숫자의 뒷 인덱스부터 검사하도록 해보자
• 아이디어는 나왔는데 구현이 어려워서 이것저것 시도를 해봤다가, 결국 실패

const isSubsetOf = function (base, sample) {
  let result = true;
  while (sample.length > 0) {
    // 우선은, 현재값이 베이스의 범위 내에 있는지 보고, 넘어가면 리턴 폴스
    // 범위 내라면, 어디서부터 비교할지를 정해서 필요한 부분만 비교하면
    console.log(sample)
    let cur = sample.shift();
    if (cur < base[0] || cur > base[base.length - 1]) {
      return false;
    }
    let subResult = false;
    for (let e = 0; e < base.length; e++) {
      // 내부 계산에서 하나라도 맞는게 나오면 트루를 뱉고 결과에 곱연산
      if (base[e] === cur) {
        subResult = subResult || true;
      } else {
        subResult = subResult || false;
      }
      // 하나도 안겹치면 폴스를 리턴시켜서 종료
    }
    if (!subResult) return false
    result = result && subResult
  }
  return result;
};

3. 레퍼런스

const isSubsetOf = function (base, sample) {
  // 1. 집합을 정렬시켜서 검사
  // 2. 부분 검사를 하는데에 필요한 가정이 부족했음
  // 값을 기준으로 하지 말고, 인덱스를 기준으로 부분 검사를 하자
  // 3. 요소를 검사시키다, 같은 걸 찾으면 그 인덱스를 저장
  // 4. 다음 요소는 그 인덱스부터 검사
  // 5. 같은 걸 못찾으면 당연히 리턴 폴스
  base = base.sort((a, b) => {return a - b})
  sample = sample.sort((a, b) => {return a - b})
  // 0번부터 순회 시작, 갱신할 변수 선언해 놓음
  let currentIdx = 0;
  while (sample.length > 0) {
    // 결과 값 저장해줄 boolean 선언
    let result = false;
    // 0번 인덱스를 빼서 그걸 기준으로 검사 진행
    let exist = sample.shift();
    // 우선은 범위 안인지 검사 한번 해주고
    if (exist < base[0] || exist > base[base.length - 1]) {
      return false;
    }
    for (let i = currentIdx; i < base.length; i++) {
      if (exist === base[i]) {
        // 같은 값을 찾았으면, 그 값의 인덱스를 저장
        currentIdx = i;
        result = result || true;
        break; // 같은 값을 찾았으면 멈춰줘야 콜스택이 감소...
      } else {result = result || false;}
    }
    if (!result) {return false;}
  }
  return true;
};