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

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

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

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

풀이 : x, y을 기준으로 영역을 4등분하여 해당 영역의 모든 숫자가 같은 수 인지 체크한다. (divide 메서드)
수가 1이면 o(one)을, 수가 0이면 z(zero)를 ++해준다.

class Solution {
    static int z, o;
    static int [][] array;
    public int[] solution(int[][] arr) {
        array = arr;
        divide(0, arr.length, 0, arr.length);
        return new int [] {z, o};
    }
    private static void divide(int a, int b, int c, int d) {
        int cnt = 0;
        for (int i = a; i < b; i++) {
            for (int j = c; j < d; j++) {
                if(array[j][i] == 1) cnt++;
            }
        }
        if((b - a) * (d - c) == cnt) o++;
        else if(cnt == 0) z++;
        else {
            int b2 = (a + b) / 2;
            int d2 = (c + d) / 2;
            divide(a, b2, c, d2);
            divide(a, b2, d2, d);
            divide(b2, b, c, d2);
            divide(b2, b, d2, d);
        }
    }
}