2Level / 월간 코드 챌린지 시즌1 / 쿼드압축 후 개수 세기

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/68936

프로그래머스

풀이 방법

주어진 2차원 배열(정사각형 모양)을 4등분씩 나눈다음 나누어진 영역의 숫자들이 모두 같은 수라면 그 수로 압축하고,

아니라면 계속 나누고 압축하는 것을 반복해준다.

마지막으로 사각형의 크키가 1이 되면 동작을 멈춘다.

 

이 문제는 재귀를 통해 풀었다.

계산을 이어가면 갈수록 계산할 대상이 작아지고 각 영역을 나눠 계산하기 때문에 재귀가 맞다고 생각했다.

쿼드압축에 관한 글

 

코드

const solution = (arr) => {
    let answer = [0, 0];
    
    const check = (array, n) => {
        if(n === 1) {
            answer[array[0][0]] += 1;
            return;
        }
        
        let sum = array.reduce((acc, cur) => acc + cur.reduce((a, c) => a + c, 0), 0);
        
        if(sum === 0 || sum === n * n) {
            answer[array[0][0]] += 1;
            return;
        }
        else {
            check(array.slice(0, n/2).map((e) => e.slice(0, n/2)), n/2);
            check(array.slice(0, n/2).map((e) => e.slice(n/2)), n/2);
            check(array.slice(n/2).map((e) => e.slice(0, n/2)), n/2);
            check(array.slice(n/2).map((e) => e.slice(n/2)), n/2);
        }
    }
    check(arr, arr.length);
    return answer;
}