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

쿼드압축 후 개수 세기

문제링크

풀이

재귀
1. mark로 해당 부부의 0, 0 위치한 문자가 0인지 1인지 저장한다.
2. x, y로부터 각각 len 만큼 모두 mark와 같은 문자 인지 확인한다.
3. 같다면 해당 문자 개수를 1로 return 한다.
4. 만약 같지 않다면 4개의 구간으로 나눈 다음 해당 구간에서의 0, 1의 합을 return 한다.
(같지 않다면 계속해서 재귀적으로 반복된다.)

코드

class Solution {
    public int[] solution(int[][] arr) {
        
        return countNum(arr, 0, 0, arr.length);
    }
    
    public int[] countNum(int[][] arr, int x, int y, int len) {
        
        int mark = arr[x][y];
        boolean isAllSame = true;
        
        loop:
        for (int i = x; i < x + len; i++) {
            for (int j = y; j < y + len; j++) {
                if (arr[i][j] != mark) {
                    isAllSame = false;
                    break loop;
                }
            }
        }
        
        if (isAllSame) {
            int zeroCount = 0;
            int oneCount = 0;
            if (mark == 0) {
                zeroCount = 1;
            } else {
                oneCount = 1;
            }
            return new int[] {zeroCount, oneCount};
        } else {
            int newLen = len/2;
            
            int[] one = countNum(arr, x, y, newLen);
            int[] two = countNum(arr, x + newLen, y, newLen);
            int[] three = countNum(arr, x, y + newLen, newLen);
            int[] four = countNum(arr, x + newLen, y + newLen, newLen);
            
            int zeroCount = one[0] + two[0] + three[0] + four[0];
            int oneCount = one[1] + two[1] + three[1] + four[1];
            
            return new int[] {zeroCount, oneCount};
            
        }
    }
}