[ Coplit ] - 24_isSubsetOf 문제 풀이

문제

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

입력

인자 1 : base

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

인자 2 : sample

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

출력

boolean 타입을 리턴해야 합니다.

주의 사항

base, sample 내에 중복되는 요소는 없다고 가정합니다.

Advanced

시간 복잡도를 개선하여, Advanced 테스트 케이스(base, sample의 길이가 70,000 이상)를 통과해 보세요.

 

💬 코드

const isSubsetOf = function (base, sample) {
  const baseSet = new Set(base); // base 배열을 Set으로 변환

  for (let i = 0; i < sample.length; i++) {
    if (!baseSet.has(sample[i])) { // sample 배열의 요소가 baseSet에 없으면 false 반환
      return false;
    }
  }

  return true; // sample 배열의 모든 요소가 baseSet에 존재하면 true 반환
};

 

💬 풀이

• Advanced 테스트 케이스를 통과하기 위해, 시간 복잡도를 개선하는 방법으로는, sample의 모든 요소가 base에 존재하지 않는 경우를 최대한 빠르게 판별하는 것
  • base 배열을 Set으로 변환하는 작업은 처음 한 번만 수행하고, 그 결과를 변수에 저장하여 활용

함수 구현 설명

1. 먼저 base 배열을 Set 객체로 변환한다.
   • Set은 중복을 허용하지 않는 자료형으로, 배열 내에 중복된 요소가 있어도 하나만 포함된다.
     base 배열 내에 존재하는 모든 요소를 중복 없이 추출한다.
2. 이후 for문을 활용하여 sample 배열의 요소를 하나씩 확인한다.
   • sample 배열의 각 요소가 baseSet에 존재하지 않으면 false를 반환
     sample 배열이 base 배열의 부분집합이 아니기 때문
3. 만약 for문을 다 돌았을 때 sample 배열의 모든 요소가 baseSet에 존재한다면, true를 반환환다.
   • sample 배열이 base 배열의 부분집합임을 의미