[Programmers / Level 2] 68936. 쿼드압축 후 개수 세기 (Java)

💡 Info

• 난이도: Lv2
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/68936
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/2/쿼드압축 후 개수 세기

입출력 조건

입출력 예시

문제 이해

• 2차원 배열을 압축하여 0과 1의 개수를 세는 문제(쿼드트리 분할 정복 사용)

알고리즘

풀이 시간 : 27분

• 현재 영역이 모두 같은 숫자인지 확인
  • 만약 0 또는 1로만 이루어져 있다면 해당 숫자의 개수를 증가
• 같지 않다면 4개로 나눠서 확인

class Solution {
    public int[] solution(int[][] arr) {
        int[] answer = new int[2];
        compress(arr, 0, 0, arr.length, answer);
        return answer;
    }

    private void compress(int[][] arr, int x, int y, int size, int[] answer) {
        if (isUniform(arr, x, y, size)) {
            answer[arr[x][y]]++;
            return;
        }

        int half = size / 2;
        int[][] offsets = {{0, 0}, {0, half}, {half, 0}, {half, half}};
        
        for (int[] offset : offsets) {
            compress(arr, x + offset[0], y + offset[1], half, answer);
        }
    }

    public boolean isUniform(int[][] arr, int x, int y, int size) {
        int val = arr[x][y];
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                if (arr[i][j] != val) return false;
            }
        }
        return true;
    }
}

결과