쿼드압축 후 개수 세기(프로그래머스) JAVA

https://school.programmers.co.kr/learn/courses/30/lessons/68936

프로그래머스

 

문제 설명

이렇게 첫 번째 영역이 주어지면 쿼드 트리와 같은 방식으로 압축하는 것 입니다. 결국 0의 갯수는 4개, 1의 갯수는 9개 입니다.

 

문제 해결 방법

재귀를 사용해서 풀어야 하는 문제입니다. 똑같은 공간으로 계속 나누므로 적절하게 점화시막만 잘 만들면 쉽게 풀 수 있을 것 같습니다. 이 문제는 정사각형으로 계속해서 분할하면서 정사각형 안이 모두 0이거나 1이면 합치는 형식입니다.

• (offsetX, offsetY, size)는 offsetX와 offsetY에서 시작하곡 각 변의 길이가 size인 정사각형을 뜻합니다. 이 사각형 안의 0과 1의 갯수를 저장합니다.
• 매 순간 4개의 정상각형으로 분할이 됩니다. 이것을 처리하기 위해 4가지 경우의 수를 만들어야 합니다.
  • offsetX, offsetY, size/2
  • offsetX+size/2, offsetY,  size/2
  • offsetX, offsetY+size/2, size/2
  • offsetX + size/2, offsetY + size/2, size/2

 

전체 코드

class Solution {
    // 0과 1의 갯수
    private static class Count{
        int zero; int one;
        public Count(int zero, int one){
            this.one = one;
            this.zero = zero;
        }
        //Count 객체를 합하는 add() 메서드 정의
        public Count add(Count other){
            return new Count(zero + other.zero, one + other.one);
        }
    }
    
    private Count count(int offsetX, int offsetY, int size, int[][] arr){
        int h = size/2;
        for(int x = offsetX; x < offsetX + size; ++x){
            for(int y = offsetY; y < offsetY + size; ++y){
                if(arr[y][x] != arr[offsetY][offsetX]){
                    // 점화식으로 4개로 분할
                    return count(offsetX, offsetY, h, arr)
                        .add(count(offsetX+h, offsetY, h, arr))
                        .add(count(offsetX, offsetY+h, h, arr))
                        .add(count(offsetX+h, offsetY+h, h, arr));
                }
            }
        }
        if(arr[offsetY][offsetX] == 1) return new Count(0,1);
        return new Count(1,0);
    }
    
    public int[] solution(int[][] arr) {
        Count answer = count(0,0,arr.length, arr);
        return new int[]{answer.zero, answer.one};
    }
}