isSubsetOf

- 문제

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

 

- 조건 

시간 복잡도를 개선하여, Advanced 테스트 케이스(base, sample의 길이가 70,000 이상)를 통과

 

const isSubsetOf = function (base, sample) {
    // 값이 있으면 COUNT +1 길이만큼 있으면 RETURN TRUE 
    // 배열 값을 정렬 
    // 숫자 크기 비교 38 55 이후X 
    // 있다면 BASE 원소 제거
    // 가운데 숫자 비교해서 
    // 처음 과 끝 사이에 포함되는 숫자인지 판별 
    // 가운데 처음 끝 어디서 가까운지 판별해서 찾기 시작 
    // 왼쪽 탐색인지 오른쪽 탐색인지 구별 
    
    base.sort((a, b) => a - b); // base 오름 차순 정렬 
    var count = 0; // 현재 부분집합 갯수 
    var front = base[0]; // 맨앞 숫자
    var pivot = base[Math.floor(base.length/2)]; // 가운데 기준점 
    var last = base[(base.length-1)]; // 맨뒤 숫자 
    
    var abs = 0; // 절대값 
    var indexr = 0; // 시작점
    var direction = true; // t = ++ , f == --
    var min = 0;
    var flag = 1; // f1 p2 l3 
    for(var i = 0 ; i < sample.length ;i++) // sample arr 
    {
        if(!(front <= sample[i]) || !(sample[i] <= last)) // 범위내 값이 없으면 서치 중단 
            continue;
      
        abs  = ((front - sample[i]) <0) ? -(front - sample[i]) : (front - sample[i]);
        min = abs;
        indexr = 0;
        direction = true; 
        
        abs = ((pivot - sample[i]) < 0) ? -(pivot - sample[i]) : (pivot - sample[i]);
        if(abs < min){
            min = abs;
            indexr = Math.floor(base.length/2);
            flag = 2;
        }
        
        abs = ((last - sample[i]) < 0) ? -(last - sample[i]) : (last - sample[i]);
        if(abs < min){
            min = abs;
            indexr = (base.length-1);
            direction = false;
            flag = 3;
        }
        //pivot 방향 
        if((flag == 2) && (sample[i] <= pivot))
           direction = false;
        
        var run = true;
        while(run)
        {
           if(base[indexr] === sample[i] ){
               count++;
               break;
           }
             
           // 증감
           if(direction == true)
               indexr++;
           else
               indexr--;
        
           //비교문 
           if((direction == true) && (indexr < base.length))
           {
                continue;
           }else if((direction == false) && (0 <= indexr)){
                continue;
           }else{
               run = false;
               break;
           }           
        }
           
        //console.log("방향 : "+direction + " flag " + flag + " 시작값: "+indexr)
    }
        if(count === sample.length)
            return true;
        else
            return false;

};

- 풀이 

1. Base 배열을 오름차순으로 정렬

2. Sample[i] 값이 Base 배열의 맨앞, 중간, 맨뒤 에서 가장 가까운값을 찾음

3. 2번을 기준으로 Sample[i]값이 인덱싱 기준점을 시작으로 인덱스 방향을 결정하여 Search   

4. 범위 값에 없는 범위는 검색하지않는다