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

 

프로그래머스

 

문제풀이

1. ( 0 , 0 ) 좌표부터 시작해서 재귀함수 사용

2. 가장 큰 정사각형부터 시작해서 압축이 되는지 확인하고 안되면 4분할 시작

처음 가장 큰 정사각형 사분할 조건 X

 

---

두번째로 큰 정사각형 쿼드압축 조건 O , 안되는 정사각형 사분할

---

사분할 후 계속 반복

---

가장 작은 정사각형으로 사분할 계속 진행

---

 

 

나의풀이 ( 코드 )

class Solution {
    
    static int[] answer = new int[2];
    
    public int[] solution(int[][] arr) {
        
        quad(arr, 0, 0, arr.length);
        
        return answer;
    }
    
    static boolean check(int[][] arr, int x, int y, int size) {
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                if (arr[i][j] != arr[x][y]) {
                    return false;
                }
            }
        }
        return true;
    }

    static void quad(int[][] arr, int x, int y, int size) {
        if (check(arr, x, y, size)) {
            answer[arr[x][y]]++;
            return ;
        }

        quad(arr, x, y, size / 2);
        quad(arr, x, y + size / 2, size / 2);
        quad(arr, x + size / 2, y, size / 2);
        quad(arr, x + size / 2, y + size / 2, size / 2);

    }
    
}