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

2026.10.11

문제 풀이

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

class Solution {
    private int[] result = new int[2];
    public int[] solution(int[][] arr) {
        compress(arr, arr.length, arr[0][0], 0, 0);
        
        return result;
    }
    private void compress(int[][] arr, 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(arr, size / 2, arr[row][col], row, col);
                    compress(arr, size / 2, arr[row][size / 2 + col], row, size / 2 + col);
                    compress(arr, size / 2, arr[size / 2 + row][col], size / 2 + row, col);
                    compress(arr, 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;
    }
}

문제 풀이 후기

compress 의 매개변수를 넣을 때, size 가 현재 배열의
상대 위치를 고려하지 않고 전체 배열의 전체적인 크기를 기준으로 넘겨졌다.

코드에 직접 값을 대입하면서 실패 원인을 분석하고자 했다.
그러나 찾지 못하고 AI의 도움을 받았다.
한줄한줄 실행하면서 확인을 해야 하지만, 당연히 맞다고 생각하며 특정 부분은 "내가 설계한대로 작동하겠지" 라는 안일한 생각으로 넘겨버렸다.

오래 걸리고 꼬이더라도 하나씩 차근차근 대입해보며 당연히 맞다는 생각을 버린채로 코드를 점검하는 습관을 가져야
직접 오류를 분석할 수 있는 사고방식을 기를 수 있다.