프로그래머스 쿼드압축 후 개수 세기 (JAVA)

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

코딩테스트 연습 - 쿼드압축 후 개수 세기

 

저는 재귀를 통해 해당 문제를 해결하였습니다.

재귀를 통해 해당 길이만큼의 사각형이 같은 숫자인지를 확인하고 같다면 해당 결과값을 늘려주고, 다른 것이 있다면, 재귀로 길이를 반으로 줄이고 다시 같은 숫자인지를 확인하였습니다.

 

import java.util.*;
class Solution {
    public int[] solution(int[][] arr) {
        int[] answer = new int[2];
        divideArea(0,0,arr.length,arr,answer);
        return answer;
    }
    private boolean checkSame(int y,int x,int length, int[][] arr){
        int num = arr[y][x];
        for(int i = y ; i < y+length ; i++){
            for(int j = x ; j < x+length ; j++){
                if(num != arr[i][j]){
                    return false;
                }
            }
        }
        return true;
    }
    private static final int ONE = 1;
    private static final int ZERO = 0;
    
    private void divideArea(int y,int x,int length,int[][] arr,int[] result){
        if(checkSame(y,x,length,arr)){
            if(arr[y][x] == ONE){
                result[ONE]++;
            }else{
                result[ZERO]++;
            }
            return ;
        }
        int nextLength = length / 2;
        for(int i = 0 ; i < 2; i++){
            for(int j = 0 ; j < 2; j++){
                divideArea(y +i *nextLength, x +j *nextLength, nextLength, arr, result);
            }
        }
    }
}