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

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

프로그래머스

문제 설명

재귀를 활용한 배열 탐색 문제이다. 문제를 보고 재귀적으로 나누어나가면서 범위별로 탐색해야 한다는 접근 방법은 알았으나 구현 단계에서 접근을 잘못해서 시간이 걸렸다. 처음에는 배열의 범위 길이를 넣고 이를 나누어나가면서 탐색하려 했으나 0과 2에 대한 처리가 잘 되지 않았다. 그래서 0부터 추가하는 방식으로 변경하였고 이를 통해 해결하였다.

코드

class Solution {
    private int zeros = 0;
    private int ones = 0;
    
    public int[] solution(int[][] arr) {
        int[] answer = new int[2];
        int N = arr.length;
        
        zip(arr, 0, 0, N);
        
        answer[0] = zeros;
        answer[1] = ones;
        
        return answer;
    }
    
    private boolean check(int[][] arr, int n, int m, int size, int val) {
        for (int i = n; i < n + size; i++) {
            for (int j = m; j < m + size; j++) {
                if (arr[i][j] != val) {
                    return false;
                }
            }
        }
        
        return true;
    }
    
    private void zip(int[][] arr, int n, int m, int size) {
        if (check(arr, n, m, size, arr[n][m])) {
            if (arr[n][m] == 0) {
                zeros++;
            } else {
                ones++;
            }
            return;
        }
        
        zip(arr, n, m, size / 2);
        zip(arr, n, m + size / 2, size / 2);
        zip(arr, n + size / 2, m, size / 2);
        zip(arr, n + size / 2, m + size / 2, size / 2);
    }
}