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

2026.09.19

문제 풀이

이전 AI 코드

---

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

---

class Solution {
    int[] result;
    public int[] solution(int[][] arr) {
        result = new int[2];
        compress(arr, 0, 0, arr.length);
        
        return result;
    }
    public void compress(int[][] arr, int r, int c, int size) {
        int first = arr[r][c];
        for (int i = r; i < r + size; i++) {
            for (int j = c; j < c + size; j++) {
                if (first != arr[i][j]) {
                    int half = size / 2;
                    compress(arr, r, c, half);
                    compress(arr, r, c + half, half);
                    compress(arr, r + half, c, half);
                    compress(arr, r + half, c + half, half);
                    return; 
                    // first와 다르다면 더 이상 비교할 필요가 없기 때문에 return
                }
            }
        }
        result[first]++;
    }
}

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 r, int c, int size) {
        if (isUniform(r, c, size)) {
            result[arr[r][c]]++;
            return;
        }
        int half = size / 2;
        compress(r, c, half);
        compress(r, c + half, half);
        compress(r + half, c, half);
        compress(r + half, c + half, half);
    }

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

문제 풀이 후기

이번 문제를 풀면서 지금껏 잘못된 공부를 하고 있었다는 것을 알았다.

첫번째로 문제를 풀면서 "어떤 규칙이 있는가?"를 먼저 생각하지 않았다.

두번째로 무조건 흐름대로 문제를 풀려고 했다는 것이다.
"어떤 자료구조를 사용해야 효율적으로 풀 수 있지?"라는 고민을 하지 않고
무작정 배열, Hash 등 1차원적인 풀이 방식으로만 접근을 했다.

세번째로 AI가 보여준 모범 답안을 나의 것으로 만들지 않았다.
물론 코드가 어떤 과정으로 진행되는지 눈으로 훑으며 이해하긴 했지만,
손으로 직접 짜 보는 경험 없이 끝내서 놓치는 부분이 꽤나 많았다.

위의 3가지를 생각하면서 코테를 한다면 분명 실력이 향상될 것이라 생각한다.