쿼드압축 후 개수 세기

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

프로그래머스

 

 

전체 영역을 기준으로 압축 가능여부를 살피고,

 

압축이 불가능하다면 4등분 하여 해당 영역을 기준으로 압축 가능 여부를 살피고..

 

위 행동을 계속 반복해야하므로 재귀를 사용했다.

 

0, 1 개수 카운트는 매회 압축이 가능할때마다 총 0, 1 개수에서 영역 크기 - 1 을 빼주는 방식으로 계산했다.

 

 

class Solution {
    public int[] solution(int[][] arr) {
        
        int[] answer = new int[2];
        
        divde(answer, arr, arr.length, 0, 0);
        
        return answer;
    }
    
    
    void divde(int[] answer, int[][] arr, int size, int x, int y) {
        
        if (size < 2) return;
        
        int sum = 0;
        
        for (int i = 0; i < size; i++) {
            
            for (int j = 0; j < size; j++) {
                
                int num = arr[x + i][y + j];
                
                if (arr.length == size) answer[num]++;
                
                sum += num;
                
            }
            
        }
        
        // System.out.printf("%d : (%d, %d) -> %d\n", size, x, y, sum);
        
        if (sum != 0 && sum != size * size) {
            
            size /= 2;
            
            divde(answer, arr, size, x, y);
            
            divde(answer, arr, size, x + size, y);
            
            divde(answer, arr, size, x, y + size);
            
            divde(answer, arr, size, x + size, y + size);
            
        } else {
            
            // System.out.printf("%d : 3 감소\n", arr[x][y]);
            answer[arr[x][y]] -= (size * size - 1);
            
        }
        
    }
}