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

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

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

2021-08-07

---

class Solution {
   static int zero, one;
    static void solve(int size, int x, int y, int[][] arr) {
        if(size == 1) {
            if(arr[x][y] == 0)zero++;
            else one++;
            return;
        }
 
        if(check(size, x,  y, arr)) {
            return;
        }
        solve(size/2, x, y, arr);
        solve(size/2, x, y+size/2, arr);
        solve(size/2, x+size/2, y, arr);
        solve(size/2, x+size/2, y+size/2, arr);
    }
 
    static boolean check(int size, int x, int y, int[][] arr) {
        int num = arr[x][y];
        for(int i = x; i < x+size; i++) {
            for(int j = y; j < y+size; j++) {
                if(arr[i][j] != num) return false;
            }
        }
 
        if(num == 0) zero++;
        else one++;
        return true;
    }
    static int[] solution(int[][] arr) {
        zero = 0;
        one = 0;
        solve(arr.length, 0, 0, arr);
 
        return new int[]{zero, one};
    }
}

#문제풀이

분할정복으로 풀었다.