[JAVA] [분할정복] Pro 쿼드압축 후 개수 세기

문제

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

프로그래머스

코드

import java.util.*;

class Solution {
    ArrayList<Integer> answer=new ArrayList<>();
    
    public void recur(int[][] arr, int n){
        int temp=0;
        // 배열의 모든 요소를 더함
        for(int i=0; i<arr.length; i++){
            for(int j=0; j<arr[0].length; j++){
                temp+=arr[i][j];
            }
        }
        // 모든 요소의 합이 0이면 압축 가능하므로 0추가
        if(temp==0){
            answer.add(0);
        }
        // 모든 요소의 합이 n*n이면 압축 가능하므로 1추가
        else if(temp==(n*n)){
            answer.add(1);
        }
        // 둘 다 아닌 경우 분할
        else{
            int[][] tempArray=new int[n/2][n/2];
            for(int i=0; i<n/2; i++){
                for(int j=0; j<n/2; j++){
                    tempArray[i][j]=arr[i][j];
                }
            }
            recur(tempArray,n/2);
            
            tempArray=new int[n/2][n/2];
            for(int i=0; i<n/2; i++){
                for(int j=n/2; j<n; j++){
                    tempArray[i][j-(n/2)]=arr[i][j];
                }
            }
            recur(tempArray,n/2);
            
            tempArray=new int[n/2][n/2];
            for(int i=n/2; i<n; i++){
                for(int j=0; j<n/2; j++){
                    tempArray[i-(n/2)][j]=arr[i][j];
                }
            }
            recur(tempArray,n/2);
            
            tempArray=new int[n/2][n/2];
            for(int i=n/2; i<n; i++){
                for(int j=n/2; j<n; j++){
                    tempArray[i-(n/2)][j-(n/2)]=arr[i][j];
                }
            }
            recur(tempArray,n/2);
        }
        
    }
    
    public int[] solution(int[][] arr) {
        int[] result=new int[2];
        
        int n=arr.length;
        // 분할 정복 함수 호출
        recur(arr, n);
        
        for(int i=0; i<answer.size(); i++){
            if(answer.get(i)==0){
                result[0]++;
            }
            else{
                result[1]++;
            }
        }
        
        return result;
    }
}

시간 복잡도

O(2^20+ 4*2^18+
   2^18+ 4*2^16+
   2^16+ 4*2^14+

   ...)