[JS] 쿼드압축 후 개수 세기

문제의 유형이 같은 그림이 반복되면서 줄어드는것으로 보아 재귀함수를 활용해서 풀면 효율적일 것이라 생각했다.

 

 

기본적인 큰 틀로, 배열을 넣으면 0의 개수와 1의 개수를 반환해주는 함수를 만들었다.

 

1번 종료조건으로 만약 길이가 1이라면 해당 값을 배열에 담아서 리턴을 해주었고

2번 종료조건으로 모든 수가 같다면 해당 값을 배여렝 담아서 리턴해주었다.

 

그렇지 않다면 배열을 1/4씩 쪼개어 4번 재귀함수를 호출한 후, 그로구한 1과 0의 개수를 더해서 return해주었다.

 

const recur = (arr) => {
    if (arr.length===1) return arr[0][0] ? [0,1] : [1,0]
    
    const std = arr[0][0]
    const halfLen = arr.length / 2
    let isSameNum = true
    
    outer : for (let i = 0 ; i < arr.length ; i++) {
        for (let j = 0 ; j < arr.length ; j++) {
            if (arr[i][j]!== std) {
                isSameNum = false;
                break outer
            }
        }
    }
    
    if (isSameNum) return arr[0][0] ? [0,1] : [1,0]
    
    let ret = [0,0]
    for (let i = 0 ; i <= halfLen ; i += halfLen) {
        for (let j = 0 ; j <= halfLen; j+= halfLen) {
            const [zero,one] = recur(arr.slice(i,i+halfLen).map(v => v.slice(j,j+halfLen)))
            ret[0] += zero
            ret[1] += one
        }
    }
    return ret
}

function solution(arr) {
    return recur(arr)
}