03_isSubsetOf

---

문제

---

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

입력

---

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

수도코드

---

for문으로 base 기준으로 sample[i]값을 includes해서 답을 구하면
짧은 길이의 배열에는 문제가 없으나,
Advanced처럼 길이가 70,000 이상인 경우에는 처리하기 어렵다.
따라서
sort를 이용해 오름차순으로 base, sample을 정렬하고
sample에 for문을 이용해서 base배열에 해당 값을 넣어
일치하는 값이 나오는지 확인/ base값이 sample값보다 커지면 false

Code

---

const isSubsetOf = function (base, sample) {
	// TODO: 여기에 코드를 작성합니다.
  // base = [10, 99, 123, 7] / sample = [11, 100, 99, 123]; 를 예시로 들어보자. 
  // sort를 이용해서 오름차순으로 정렬
  // base = [7, 10, 99 ,123]
  // sample = [11, 99, 100, 123]
  base.sort((a,b) => a - b);
  sample.sort((a,b) => a - b);
  
  // sample 요소가 base 요소에 속하는지 확인하는 함수
  const findFunc = (item, arr, from) => {
    // i=from으로 하는 이유는 이미 앞의 배열에서 부터 확인을 진행했기 때문에 다음 요소를 찾을 때 그 이후부터 진행
  	for(let i=from; i<arr.length; i++){
      	// 11 !== 7이므로 성립 X
    	if(item === arr[i]) return i;
      	// 11 < 7이 성립하지 않으므로 다음 i값으로 넘어간다.
      	else if(item < arr[i]) return -1;
      // 11 !== 10 X
      // 11 < 10 X 다음 i 값으로
      // 11 !== 99 X
      // 11 < 99 O 성립 return -1;
    }
    return -1;
  };
  
  // from 초기값
  let baseIdx = 0;
  // findFunc의 인자를 지정하고 결과에 따라 false 생성
  // sample.length = 4
  for(let i=0; i<sample.length; i++) {
    // findFunc(11, base, 0) 삽입
  	baseIdx = findFunc(sample[i], base, baseIdx);
    // 결과가 -1이므로 아래 조건 성립
    if(baseIdx === -1) return false;
  }
  return true;
};

키워드

• sort()