[프로그래머스/LV2] 쿼드압축후 개수 세기 - 재귀(Java)

[프로그래머스 월간 코드챌린지 시즌1] 쿼드압축 후 개수 세기

🙋‍♂️ 들어가며

0과 1로 이루어졌다. n^2 * n^2

압축할 특정영역 S가 존재하는데, 만약 S 내부의 모든 수가 같으면 한가지 수로 압축한다. -> 최종적으로 남은 0, 1 갯수를 저장한다

우선 N <= 10 으로

재귀를 통해 한변의 길이가 절반으로 줄어들기에 최종적으로 아래와 같이 될 것이다.

\[\frac{N}{2^k} = 1\]

따라서

\[N = 2^k\]

이므로

\[\log_2 N = k\]

시간복잡도를 N^2 * log N 으로 4분할하여 풀 수 있겠다는 생각이 들었다

아이디어

// 1. main
    // 1-1. 첫 시작 행, 열 = 0;
    // 1-2. 첫 길이 N
    // 1-3. quad_tree 함수

// 2. quad_tree 함수
    // 2-1. 격자 안의 값이 첫값과 다 같은지 확인
        // 2-1-a. 만약 1개라도 틀리면 false
    // 2-2. 만약 전부 같으면 arr[첫값]++ 후에 return

    // 2-3. 한개라도 틀려서 압축 못했을 시
    // -> 다음 행, 열 = 현재좌표로 갱신, 배열크기 -> 절반
    // 그리고 백트랙킹 각각(왼위, 오위, 왼아래, 오아래)

testcase

{
    {1,1,1,1,1,1,1,1},
    {0,1,1,1,1,1,1,1},
    {0,0,0,0,1,1,1,1},
    {0,1,0,0,1,1,1,1},
    {0,0,0,0,0,0,1,1},
    {0,0,0,0,0,0,0,1},
    {0,0,0,0,1,0,0,1},
    {0,0,0,0,1,1,1,1}
}

내 생각대로 [10, 15] 가 출력되었다

✅ 코드

class Solution {
    static int[] answer;
    
    public int[] solution(int[][] arr) {
        answer = new int[2];
        
        // 1. quad_tree
        int sr = 0;
        int sc = 0;
        int N = arr.length;
        quad_tree(sr, sc, arr, N);
        
        // 2. 결과값
        return answer;
    }
    
    
    
    // 3. quad_tree 함수
    static void quad_tree(int cr, int cc, int[][] arr, int N) {
        
        // 3-1-a. 격자 안의 값이 첫 값과 다 같은지 확인
        int point = arr[cr][cc];
        boolean is_all_same = true;
        for (int r = cr; r < cr + N; r++) {
            for (int c = cc; c < cc + N; c++) {
                // 3-1-b. 1개라도 틀리면 종료
                if (arr[r][c] != point) {
                    is_all_same = false;
                    break;
                }
            }
            // 3-1-c. 이미 1개라도 틀렸으면 break
            if (!is_all_same) break;
        }
        
        // 3-1-d. 만약 전부 같으면 -> 좌표 압축하고, 종료
        if (is_all_same) {
            answer[point]++;
            return;
        }
        
        
        // 3-2. 1개라도 틀려서 압축 못했을시
        int nr = cr;
        int nc = cc;
        int half = N / 2;
        
        // 3-3. 재귀
        
        // 3-3-a upper_left
        quad_tree(nr, nc, arr, half);
        
        // 3-3-b. upper_right
        quad_tree(nr, nc + half, arr, half);
        
        // 3-3-c. down_left
        quad_tree(nr + half, nc, arr, half);
        
        // 3-3-d. down_right
        quad_tree(nr + half, nc + half, arr, half);
    }
    
    
}