쿼드압축 후 개수 세기

사용 알고리즘: 재귀

사용 언어: java

 

import java.util.*;

class Solution {
    int[] answer = new int[2];
    
    public int[] solution(int[][] arr) {
        int len = arr.length;
        divideArr(arr, len);
        
        return answer;
    }
    
    public void divideArr(int[][] arr, int len) {
        int n = len;
        if(len == 1) {
            answer[arr[0][0]]++;
            return;
        }
        
        int sum = 0;
        for(int i=0; i<len; i++) {
            for(int j=0; j<len; j++) {
                sum += arr[i][j];
            }
        }
        
        if(sum==0) {
            answer[0]++;
            return;
        }
        if(sum == len*len) {
            answer[1]++;
            return;
        }
        
        //압축 불가ㅠ
        int[][] nextArr = new int[len/2][len/2];
        ㅁ
        //1
        for(int i=0; i<len/2; i++) {
            for(int j=0; j<len/2; j++) {
                nextArr[i][j] = arr[i][j];
            }
        }
        divideArr(nextArr, len/2);
        
        //2
        for(int i=0; i<len/2; i++) {
            for(int j=len/2; j<n; j++) {
                nextArr[i][j-len/2] = arr[i][j];
            }
        }
        divideArr(nextArr, len/2);
        
        //3
        for(int i=len/2; i<n; i++) {
            for(int j=0; j<len/2; j++) {
                nextArr[i-len/2][j] = arr[i][j];
            }
        }
        divideArr(nextArr, len/2);
        
        //4
        for(int i=len/2; i<n; i++) {
            for(int j=len/2; j<n; j++) {
                nextArr[i-len/2][j-len/2] = arr[i][j];
            }
        }
        divideArr(nextArr, len/2);
    }
}

 

캬 시간초과가 안 나다ㅣㄴ