알고리즘 - 쿼드압축 후 개수 세기

문제

• divide-and-conquer

• 링크

코드

function solution(arr) {
    let answer = [0,0];
    
    const test = (arr, size) => {
        
        let value = arr.reduce((sum, arr1)=>{
            let sum1 = arr1.reduce((a,b)=>{
                return a+b;
            },0);
            return sum1 + sum;
        },0);
        
        //console.log(value)
        let check =  (value / (size*size));
        if(check === 1
          || check === 0){
            
            answer[(value / (size*size))]++;
            return;
        }
        
        let leftUpArr = 
            arr.slice(0,size/2)
            .map((el)=>el.slice(0,size/2));
        let rightUpArr =
            arr.slice(0,size/2)
            .map(e1=>e1.slice(size/2,size));
        let leftDownArr =
            arr.slice(size/2, size)
            .map(e1=>e1.slice(0, size/2));
        let rightDownArr =
            arr.slice(size/2, size)
            .map(e1=>e1.slice(size/2, size));
        
        test(leftUpArr, size/2);
        test(rightUpArr, size/2);
        test(leftDownArr, size/2);
        test(rightDownArr, size/2);
        
    }
    test(arr, arr.length);
    
    return answer;
}

회고

• map, slice, reduce 같은 메소드들을 잘 활용해야 한다