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

문제출처

const divide = (arr, answer, [x, y], size) => {
    const first = arr[x][y];
    
    if (size === 1) {
        first === 0 ? answer[0]++ : answer[1]++;
        return;
    }
    
    const half = size / 2;
    let flag = false;
    for (let i=x; i<x+size; i++) {
        for (let j=y; j<y+size; j++) {
            if (arr[i][j] !== first) {
                flag = true;
                break;
            }
        }
    }
    
    if (!flag) { // 모두 다 같은 경우
        first === 0 ? answer[0]++ : answer[1]++;
        return;
    }
    
    divide(arr, answer, [x, y], half);
    divide(arr, answer, [x, y + half], half);
    divide(arr, answer, [x + half, y], half);
    divide(arr, answer, [x + half, y + half], half);
};

function solution(arr) {
    const answer = [0, 0];
    divide(arr, answer, [0, 0], arr.length);
    return answer;
}

풀이

• 분할정복기법을 사용해 재귀적으로 해결
• 계속 4등분을 하면 되는 문제

참고