[Algorithm] 시간복잡도 개선 부분집합 문제

 

문제

 

두개의 배열 base, sample을 입력받아 sample이 base의 부분 집합인지 여부를 확인 후 boolean값을 반환하라. base, sample 배열은 number 타입 요소를 가진다.

 

제약조건

• base.length > 70,000
• sample.length > 70,000

 

 

소스코드 구현

 

첫번째 솔루션

시간복잡도를 고려하지 않는다면 단순하게 문제를 풀 수 있다. 두개의 반복문을 순회하면서 sample의 요소와 base 요소를 비교하면서 결과값을 result 배열에 담아 출력하면 된다.

 

const isSubsetOf = function (base, sample) {
    let result = new Array(sample.length).fill(false);

    for(let i=0; i<sample.length; i++){
        for(let j=0; j<base.length; j++){
            if(sample[i] === base[j]) result[i]=true;
        }
    }
    return !result.includes(false);
  };

 

 

진짜 문제는 base, sample 배열 길이가 70000 이상인 경우다. 시간복잡도가 증가하면서 메모리 사용량이 급증하게 되고 fail이 발생한다.

const base = [...Array(70000).keys()]
const sample = [...Array(70000].keys()]

 

두번째 솔루션

시간복잡도 문제를 해결하기 위해서 number 타입의 요소를 가진 배열을 sorting 해주고, 순회 횟수를 획기적으로 줄이는 방법이 필요하다. 여기서 사용하는 방법은 두번째 반복문에 현재 위치값을 전달해주는 것이다.

 

① 주어진 배열 base와 sample을 sort한다. 순차적으로 검색을 하기 위함이다.

base.sort((a,b)=>a-b);
sample.sort((a,b)=>a-b);

 

② base 배열을 순회하는 함수를 새로 작성한다. 특이점은 인자로 (순회할 배열,  비교값, 현재 위치) 3개를 던져주는 것이다.

반복문은 현재 위치 부터 순회하기 시작하고, 만약 비교값과 현재값이 같으면 반복문 내 현재 위치를 반환하고, 만약 현재값이 현재 위치(idx)보다 크거나 작은 경우 -1을 반환한다. 

const findIdx = (arr, idx, from) =>{
    for(let i=from; i<arr.length; i++){
        if(arr[i]===idx) return i;
        else if(arr[i]>idx) return -1;
    }
    return -1;
}

 

③ 마지막으로 sample 배열을 순회한다. 현재 위치(baseIdx)는 0부터 시작하고, 만약 비교값과 같은 값을 찾지 못하는 경우 -1을 반환받아 false를 반환하고 종료한다. 

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

 

 

전체 소스

const isSubsetOf = function (base, sample) {

    base.sort((a,b)=>a-b);
    sample.sort((a,b)=>a-b);


    const findIdx = (arr, idx, from) =>{
        for(let i=from; i<arr.length; i++){
            if(arr[i]===idx) return i;
            else if(arr[i]>idx) return -1;
        }
        return -1;
    }

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

 

 

Reference

• 시간복잡도란?

 

 

정리

 

알고리즘 문제에서 시간 복잡도는 중요한 문제다. 백준 알고리즘에서도 메모리 초과가 뜨면서 실패하는 경우가 적지 않다. 분명 로직은 모두 맞음에도 불구하고 실패가 나는 경우는 대부분 시간복잡도 문제를 해결하지 못한 경우다.

 

실제 프로젝트를 진행할 때도 더 적은 연산으로 같은 결과를 낼 수 있는 경우가 얼마든지 있다. 1개의 연산이라도 덜 하고, 1개의 코드라도 덜 넣어서 코드를 작성하는 습관을 가져야 할 필요가 있다.

 

 

 

[Algorithm] Queue 알고리즘 Printer Spooler 구현하기