알고리즘 문제풀이 - toy isSubsetOf 문제

문제에 앞서 문제 이름이 isSubsetOf니까 subset의 뜻이 뭔지 확인해보면 다음과 같다. 

영어 사전에서 subset 의 정의

사전의 부분 집합의 정의는 멤버가 주어진 클래스의 모든 멤버 인 집합입니다. A는 B의 하위 집합으로 보통 A⊆B로 작성됩니다. 부분 집합의 다른 정의는 더 큰 집합 내의 집합입니다.

부분집합 링크 

subset - 네이버 영어사전 링크

SUBSET - 영어사전에서 subset 의 정의 및 동의어

문제 설명

이 문제는 집합 2개를 입력으로 받는다. 그 중 sample 집합이 base라는 본 집합의 부분집합인지 여부를 확인하고 boolean 값으로 리턴해주는 문제이다. 대신 시간복잡도를 생각해서 풀어야한다. 

입력

인자 1 : base

• number 타입을 요소로 갖는 임의의 배열
• base.length는 100 이하

인자 2 : sample

• 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 이상)를 통과해 보세요.

 

나는 처음에는 그냥 이중 반복문으로 빨리 푸려고 했으나 역시나 시간복잡도가 문제였다. 그래서 테스트 통과가 되지않았다.

그래서 두번째로는 두 배열을 합치고 중복이 된다면 객체로 계산했을 때 밸류값이 2가될 것이라고 생각했고 최후에 반복문을 돌려서 2인 배열요소의 숫자와 sample의 배열요소의 숫자가 같다면 부분집합이 되겠다고 생각했다. 그래서 다음과 같이 코드를 풀었다.

 

// const isSubsetOf = function (base, sample) {
//   // TODO: 여기에 코드를 작성합니다.
//   중첩반복문? 을 사용했으나 시간복잡도 개선 실패함
//   let count = 0;
//   for (let i = 0; i < sample.length; i++) {
//     for (let j = 0; j < base.length; j++) {
//       if (sample[i] === base[j]) {
//         count += 1;
//       }
//     }
//   }
//   if (count === sample.length) {
//     return true;
//   } else {
//     return false;
//   }
// };


const isSubsetOf = function (base, sample) {
  //2개 배열을 합친다. 
  result = base.concat(sample);
  
  // 합친 배열에서 중복되는 객체를 카운트한다. 
  const result2 = result.reduce((accu, curr) => {
    accu[curr] = (accu[curr] || 0) + 1;
    return accu;
  }, {});

  //   테스트시 로그확인
  //   console.log("result", result2);
  //   console.log(Object.values(result2));

  //final에 객체의 모든 밸류값을 넣었다. 
  let final = Object.values(result2);
  let count = 0;
  for (let i = 0; i < final.length; i++) {
    if (final[i] === 2) {
    //객체의 모든 밸류값 중 중복되는 배열요소가 있을 때마다 1씩 플러스
      count += 1;
    }
  }
  // 중복되는 배열요소카운트 === 샘플 집합 배열요소의 길이 >> 반환타입은 boolean
  return count === sample.length;
};


//다음은 node로 실행할 때 확인하기 위한 테스트 코드 
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