부분집합인지 확인하기

문제

두 개의 배열(base, sample)을 입력받아 sample이 base의 부분집합인지 여부를 리턴시켜라

const isSubsetOf = function(base,sample) {
  
  //base와 sample을 오름차순으로 정렬한다
  base.sort((a,b) => a-b);
  sample.sort((a,b) => a-b);
  
  //함수를 정의한다
  //오름차순으로 정렬된 arr을 반복문으로 방문하여 item이 존재하는지 확인하여 
    //존재하면 arr의 인덱스+1을 리턴하고
    //존재하지 않으면 -1을 리턴한다.
  const findItemInSortedArr = (item, arr, from) => {
    for(let i=from; i<arr.length; i++){
      if(item === arr[i]) return i+1;
      else if(item < arr[i]) return -1
    }
    return -1;
  }
  
  //정의한 함수를 활용한다
  let baseIdx = 0;
  for(let i=0; i<sample.length; i++){
    baseIdx = findItemInSortedArr(sample[i],base,baseIdx);
    if(baseIdx === -1) return false
  }
  return true;
}

왜 오름차순으로 정렬해?

sample을 방문해 모든 요소를 꺼내와 base에 존재하는지를 확인해야 한다.이때, 두 배열을 오름차순으로 정리해두면, base에 존재하는 sample의 요소의 인덱스 다음부터 확인하면 되기 때문이다. 예를 들어,

const sample = [6,7];
const base = [1,2,3,4,5,6,7]; 

두개의 배열이 오름차순으로 정렬되었고, sample[0] === 6이라면,

base에 6이 존재하는지를 확인하기 위해 차례로 base의 요소를 방문하다가 5번째에서 찾게 된다.
이것이 의미하는 것은 base[6]은 무조건 sample[0]보다 크다는 것이다.

따라서 sample[1]이 base에 존재하는지를 확인하기 위해서 다시 base의 0번째 요소부터 방문할 필요가
없는 것이다. 대신 6번째부터 방문하면 된다. 이미 5번째에서 6이라는 요소를 찾았고, 6번째가 존재한다면 요소는 무조건 6초과일 것이므로 앞의 요소들은 확인하지 않아도 되는 것이다.

즉, 오름차순으로 정렬하고 base의 인덱스를 기억해두면, 그것보다 1큰 인덱스부터 다시 base를 방문하면 되어 시간이 단축된다.

정의된 함수 findItemInSortedArr 살펴보기

for(let i=from; i<arr.length; i++){
  if(item === arr[i]) return i+1;
  else if(item < arr[i]) return -1
}

반복문 내에 리턴 조건이 2개가 있는데,
첫번째로, sample의 요소가 arr[i]와 일치하면 i+1을 리턴시키고, 이는 baseIdx에 저장된다.
둘째로, sample의 요소가 arr[i]보다 작으면, -1을 리턴시키고, 이는 baseIdx에 저장된다.

item < arr[i]라는 조건이 있는 이유는 왜일까?

이는 다시 오름차순과 이어진다. item === sample[0]인 경우, sample과 base의 가장 첫번째 요소이자 가장 작은 값을 비교하게 된다. 이때, base의 가장 작은 값이 sample의 것보다 크다면, base에는 sample[0]이 절대 존재할 수 없다는 것을 의미한다.

따라서, 이 경우에는 -1을 리턴시킨다.

주어진 두 개의 조건이 아닌 경우는?

const sample = [6,7];
const base = [1,2,3,4];

sample[0] === 6이므로 base에 6이 존재하는지 확인하기 위해 i를 1씩 증가시키며 base 배열의 요소를 탐색할 것이다. 하지만, 같은 요소를 찾을 수 없고, base의 모든 요소들이 6보다 작으므로 반복문이 종료된다.

따라서 반복문을 다 돌았는데도 6을 찾을 수 없다는 말은 base에 요소가 없다는 것을 의미하므로 -1을 리턴시켜야 한다.