[프로그래머스] LV 2 쿼드압축 후 개수 세기

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

프로그래머스

 

 

접근방법

1. 현재 범위에서 조건에 따라 4등분하고 다시 검사하는 반복적인 함수 호출이 일어난다 -> 재귀가 적절해보임
2. 배열을 넘겨서 해당 배열의 원소가 모두 같으면 class 변수인 ans에 기록한다.
3. 같지 않으면 4등분한 배열을 재귀적으로 다시 검사한다.
4. 길이가 1이되면 모두 같을 수 밖에 없다.

 

 

코드

class Solution {
    int[] ans = new int[2];
    public int[] solution(int[][] arr) {
        recur(arr);
        return ans;
    }
    void recur(int[][] arr){
        int num = getNum(arr);
        if(num >= 0){
            ans[num]++;
            return;
        }
        
        int size = arr.length;
        recur(copy(arr, 0,0));
        recur(copy(arr, 0,size/2));
        recur(copy(arr, size/2,size/2));
        recur(copy(arr, size/2,0));
    }
    int[][] copy(int[][] arr,int sr,int sc){
        int size = arr.length/2;
        int[][] copyArr = new int[size][size];
        
        for(int i = 0 ; i < size ; i++){
            for(int j = 0 ; j < size; j++){
                copyArr[i][j] = arr[i+sr][j+sc];
            }
        }
        return copyArr;
    }
    int getNum(int[][] arr){
        int num = arr[0][0];
        int size = arr.length;
        for(int i = 0; i <  size; i++){
            for(int j = 0; j < size ; j++){
                if(num != arr[i][j]) return -1;
            }
        }
        return num;
    }
}