[프로그래머스] 쿼드 압축 후 개수 세기

1. 문제

쿼드 압축 후 개수 세기
https://school.programmers.co.kr/learn/courses/30/lessons/68936

2. 기존 풀이

재귀, 분할정복 풀이 방법을 구상해야 했다.

function solution(arr) {
    var answer = [];
    
    function quad(x, y, len){
        if(len === 1){
            answer.push(arr[x][y])
            return
        }
        let brr = []
        
        for(let i = 0; i < len; i++){
            for (let j =0 ; j < len; j++){
                brr.push(arr[x+i][y+j])
            }
        }
        brr = [...new Set(brr)]
        
        if(brr.length === 1) {
            answer.push(brr[0])
            return
        }
        else{
            quad(x,y,len/2)
            quad(x+len/2,y,len/2)
            quad(x,y+len/2,len/2)
            quad(x+len/2,y+len/2,len/2)
        }
    }
    quad(0,0,arr.length)
    
    const count = [0,0]
    console.log(answer)
    answer.map(i => {
        if(i === 1){
            count[1] +=1
        }
        else{
            count[0] +=1
        }
    })
    return count;
}

3. 고수의 풀이

function solution(arr) {
    const quadZip = (row, col, n) => {
        if(n < 2) return arr[row][col] ? [0, 1] : [1, 0];
        let cnt0 = 0, cnt1 = 0; n >>= 1;
        for(let [i, j] of [[0,0],[0,1],[1,0],[1,1]]) {
            let [zero, one] = quadZip(row+i*n, col+j*n, n);
            cnt0 += zero;
            cnt1 += one;
        }
        if(cnt0 === 0) return [0, 1];
        if(cnt1 === 0) return [1, 0];
        return [cnt0, cnt1];
    }
    return quadZip(0, 0, arr.length);
}