[프로그래머스] 쿼드압축 후 개수 세기 (월간 코드 챌린지 시즌 1)

문제 링크

programmers.co.kr/learn/courses/30/lessons/68936?language=javascript#

코딩테스트 연습 - 쿼드압축 후 개수 세기

 

풀이

재귀 함수를 이용하면 됩니다.

 

1) 배열의 모든 수의 합을 구합니다. 이때 n차원 배열을 풀어주는 flat() 함수를 이용하면 편합니다. flat() 함수는 ES10에서 추가되었습니다.

2) 위에서 구한 합이 0이거나 원소의 개수와 같다면 [1, 0] 또는 [0, 1]을 반환해줍시다.

3) 그렇지 않으면 배열을 4등분하여 다시 함수의 인자로 넘겨줍니다.

 

 

정답 코드

const go = (arr) => {
    let l = arr.length;
    const sum = arr.flat().reduce((acc, v) => acc + v, 0);
    if(sum === 0) return [1, 0];
    else if(sum === l*l) return [0, 1];
    
    let ret = [0, 0];
    l /= 2;
    for(let i = 0; i < 2; i++){
        for(let j = 0; j < 2; j++){
            const next = arr.slice(i*l, i*l+l).map(row => row.slice(j*l, j*l+l));
            const cnt = go(next);
            ret[0] += cnt[0];
            ret[1] += cnt[1];
        }
    }
    return ret;
};
function solution(arr) {
    return go(arr);
}