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

코드 힌트

1. 문제의 핵심:
   • 2차원 배열에서 동일한 값들로 이루어진 구역을 찾아 이를 압축하는 방식입니다.
   • 압축이 가능하면 해당 구역의 숫자(0 또는 1)의 개수를 기록하고, 압축이 불가능하면 구역을 4등분하여 재귀적으로 탐색합니다.
2. 압축 조건:
   • 주어진 size 크기의 구역이 모두 동일한 값(0 또는 1)으로 이루어져 있는지 확인합니다.
   • 만약 동일하다면 해당 값을 카운트합니다.
3. 재귀적인 분할:
   • 압축이 불가능한 경우, 해당 구역을 4등분하여 각 작은 구역에 대해 다시 압축을 시도합니다.
   • 이를 통해 점점 작은 영역으로 압축을 시도하게 됩니다.
4. 결과 배열:
   • 배열 result[0]은 0의 개수를, result[1]은 1의 개수를 저장합니다.

 

---

정답은 더보기 클릭

class Solution {
    
    int[] result = new int[2]; // 0과 1의 개수를 저장할 배열
    
    public int[] solution(int[][] arr) {
        
        // 2차원 배열 arr에 대해 압축을 시작 (0,0 위치에서 arr의 전체 크기만큼)
        compress(arr, 0, 0, arr.length);
        
        return result; // 압축 결과를 반환
    }
    
    // 주어진 영역을 압축할 수 있으면 압축, 그렇지 않으면 더 작은 영역으로 분할하는 함수
    public void compress(int[][] arr, int x, int y, int size) {
        
        // 현재 크기 size의 x, y 좌표에서 압축이 가능한지 확인
        if (isAbleCompress(arr, x, y, size)) {
            // 압축이 가능하다면 해당 값(0 또는 1)을 결과 배열에 추가
            result[arr[x][y]]++;
            return; // 압축이 완료되었으므로 종료
        }
        
        // 압축이 불가능하면 영역을 4등분하여 재귀적으로 압축 시도
        int curSize = size / 2;
        
        // 4등분한 각 영역에 대해 다시 압축 시도
        compress(arr, x, y, curSize); // 왼쪽 위
        compress(arr, x, y + curSize, curSize); // 오른쪽 위
        compress(arr, x + curSize, y, curSize); // 왼쪽 아래
        compress(arr, x + curSize, y + curSize, curSize); // 오른쪽 아래
    }
    
    // 주어진 영역이 모두 동일한 숫자로 구성되어 있는지 확인하는 함수
    public boolean isAbleCompress(int[][] arr, int x, int y, int size) {
        int targetNum = arr[x][y]; // 첫 번째 숫자를 기준으로 압축 가능 여부를 확인
        
        // x, y 좌표에서 시작하는 size 크기의 영역을 모두 확인
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                // 영역 내에 다른 숫자가 있으면 압축 불가능
                if (targetNum != arr[i][j]) {
                    return false;
                }
            }
        }
        
        // 모든 숫자가 동일하면 압축 가능
        return true;
    }
}