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

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

 

분할 정복 문제

class Solution {
    static int[] answer = new int[2];
    static int[][] arr;

    static void solve(int sr, int er, int sc, int ec) {

        int v = arr[sr][sc];
        boolean end = true;

        if(sr == er) {
            answer[v]++;
            return;
        }

        for(int r=sr; r<=er; r++) {
            for(int c=sc; c<=ec; c++) {
                if(arr[r][c] != v) {
                    end = false;
                    break;
                }
            }

            if(!end)
                break;
        }

        if(end) {
            answer[v]++;
            return;
        }

        int hr = (sr + er) / 2;
        int hc = (sc + ec) / 2;

        solve(sr, hr, sc, hc);
        solve(sr, hr, hc+1, ec);
        solve(hr+1, er, sc, hc);
        solve(hr+1, er, hc+1, ec);
    }

    public int[] solution(int[][] arr) {
        this.arr = arr;
        solve(0, arr.length-1, 0, arr[0].length-1);
        return answer;
    }
}