[코플릿]isSubsetOf

코드스테이츠 과제 코드를 공부 목적으로 변형 해서 정리 하였습니다.

✅문제

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

 

⛔주의

• 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

 

🍀해결코드

const isSubsetOf = function (base, sample) {
    base.sort((a, b) => a - b)
    sample.sort((a, b) => a - b)
    
    const findIndex = (el, base, idx) => {
        for (let j = idx; j < base.length; j++) {
            if (el === base[j]) {
                return j
            } else if (el < base[j]) {
                return -1
            }
        }
        return -1
    }
    let idx = 0;
    for (let i = 0; i < sample.length; i++) {
        idx = findIndex(sample[i], base, idx)
        if (idx === -1) {
            return false
        }
    }
    return true
};

---

🦦해설

처음에 제출한 코드는 실행초과가 걸렸다.

단순하게 sample을 for문 돌려 base에 includes가 true인지만 확인했다

몰랐는데 includes는 실행 초과의 위험이 있다고 한다. 조심히 사용해야 할것같다.

 

아무튼 코드의 시간을 줄이기 위해 고민을 해보았다.

우선 sample과 base를  정렬한다.

sample의 i번째 요소가 base의 j번째 요소와 같다면, sample의 i+1번째요소는 j+1 이상 번째 에서 발견되거나, 존재하지 않는다.(smaple의 i+1번쨰 요소가 base있는지 확인할때는 처음부터가 아니라 j+1번째 부터 확인하면 된다.)

또한 발견이 안되는 요소가 있다면 그 즉시 실행을 종료하고 false를 출력한다.