쿼드압축 후 개수 세기_복습3

2026.10.13

문제 풀이

나의 코드

소요 시간: 10분
시간 복잡도: $O(n² log n)

class Solution {
    private int[][] arr;
    private int[] result = new int[2];
    public int[] solution(int[][] arr) {
        this.arr = arr;
        compress(arr.length, arr[0][0], 0, 0);
        
        return result;
    }
    private void compress(int size, int start, int row, int col) {
        if (size <= 1) {
            result[start]++;
            return;
        }
        int r = row;
        for (int i = 0; i < size; i++, r++) {
            int c = col;
            for (int j = 0; j < size; j++, c++) {
                if (arr[r][c] != start) {
                    compress(size / 2, arr[row][col], row, col);
                    compress(size / 2, arr[row][size / 2 + col], row, size / 2 + col);
                    compress(size / 2, arr[size / 2 + row][col], size / 2 + row, col);
                    compress(size / 2, arr[size / 2 + row][size / 2 + col], size / 2 + row, size / 2 + col);
                    return;
                }
            }
        }
        result[start]++;
        return;
    }
}

---

AI 코드

시간 복잡도: $O(n² log n)

class Solution {
    private int[][] arr;
    private int[] result = new int[2];

    public int[] solution(int[][] arr) {
        this.arr = arr;
        compress(0, 0, arr.length);
        return result;
    }

    private void compress(int row, int col, int size) {
        if (isUniform(row, col, size)) {
            result[arr[row][col]]++;
            return;
        }
        int half = size / 2;
        compress(row, col, half);
        compress(row, col + half, half);
        compress(row + half, col, half);
        compress(row + half, col + half, half);
    }

    private boolean isUniform(int row, int col, int size) {
        int first = arr[row][col];
        for (int i = row; i < row + size; i++)
            for (int j = col; j < col + size; j++)
                if (arr[i][j] != first) return false;
        return true;
    }
}

문제 풀이 후기

처음에는 이해가 잘 가지 않았던 재귀함수도 손에 익어 가는 느낌이 든다.
무엇이든간에 처음부터 잘 되는 것은 없다.
천천히 꾸준히 하는 습관이 가장 중요하다고 생각한다.