[프로그래머스] Lv.2 : 쿼드압축 후 개수 세기 - 자바[Java]

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

프로그래머스

 

풀이

분할정복 알고리즘을 사용했다.

 

코드

class Solution {
    static int oneCnt = 0;
    static int zeroCnt = 0;
    
    public int[] solution(int[][] arr) {
        divideConquer(0, 0, arr.length, arr);
        int[] answer = {zeroCnt, oneCnt};
        return answer;
    }
    
    static void divideConquer(int r, int c, int size, int[][] arr) {
        int num = arr[r][c];
        
        boolean flag = true;
        for (int i = r; i < r + size; i++) {
            for (int j = c; j < c + size; j++) {
                if (arr[i][j] != num) {
                    flag = false;
                    break;
                }
            }
            if (!flag) break;
        }
        
        if (flag) {
            if (num == 1) oneCnt++;
            else zeroCnt++;
        }
        else {
            divideConquer(r, c, size/2, arr);
            divideConquer(r, c + size/2, size/2, arr);
            divideConquer(r+ size/2, c, size/2, arr);
            divideConquer(r+ size/2, c+ size/2, size/2, arr);
        }
    }
}