Algorithm 4장 - isSubsetOf

isSubsetOf

문제

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

let isSubsetOf = function(base,sample){
    
}

입력

• base
  • number 타입을 요소로 갖는 배열
  • base.lenght는 100 이하
• 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]
let output = isSubsetOf(base, sample);
console.log(output)
// false

base = [10,99,123,7]
sample = [11,100,99,123]
let output = isSubsetOf(base, sample);
console.log(output)
// false

풀이

1. 각 배열을 오름차순으로 정렬한다.
2. 두 번째 for문에 각 sample[i]와 배열base, 처음엔 0번째 인덱스를 findItemInSortedArr 함수에 전달한다.
3. 전달받은 인자로 item은 sample[i]가 되고 arr는 base, from은 0이 된다.
   1. baseIdx의 초기값은 0이기 때문이다.
4. findItemInSortedArr의 for문을 돌며 sample의 요소와 base의 요소(i는 전달인자로 넘겨받은 sample의 i번째 인덱스)가 일치하면 sample[i]를 리턴하고, 리턴한 sample[i]는 baseIdx가 된다.
   1. base배열과 sample[i]를 비교하였는데 일치하는 값이 없다면 -1을 리턴한다.
5. 만약 일치한다면 baseIdx는 일치한 sample[i]가 되고, 다시 findItemInSoredArr함수를 돈다.
6. 넘겨받은 전달인자 from이 sample[i]이기 때문에 i는 넘겨받은 sample[i]값으로 시작하게 된다.
7. arr=base이기에 base의 sample[i]번째 인덱스부터 배열의 끝까지 값 중 일치하는 값이 없다면 -1을 리턴한다.
8. 배열을 전부 돌았을 때, sample의 요소 중 하나라도 base의 요소들과 일치하지 않으면 최종 baseidx는 -1값을 갖게 되며 그대로 false를 리턴하게 된다.
9. 만약 값이 있다면 두 번째 for문의 if문에 걸리지 않으므로 true를 리턴하게 된다.

const isSubsetOf = function (base, sample){
    base.sort((a,b)=> a - b);
    sample.sort((a,b)=> a - b);

    const findItemInSortedArr = (item, arr, from) => {
        for(let i = from; i < arr.length; i++){
            if(item === arr[i]) return i;
        }

        return -1;
    }

    let baseIdx = 0;
    for(let i = 0; i < sample.length; i++){
        baseIdx = findItemInSoredArr(sample[i], base, baseIdx);
        if(baseIdx === -1) return false
    }
    return true;
}