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

상태: 정사각형이 시작하는 좌표와 한 변의 크기

종료 조건: 모든 원소가 0일 때 또는 모든 원소가 1일 때

 

점화식: (x, y, size)= (x, y, size/2) + (x+size, y, size/2) + (x, y+size/2, size/2) + (x+size/2, y+size/2, size/2)

 

public class 쿼드압축_후_개수세기 {

    private static class Count{ //0과 1의 개수를 한번에 담을 수 있는 클래스
        public final int zero;
        public final int one;

        public Count(int zero,int one){
            this.zero=zero;
            this.one=one;
        }
        public Count add(Count other) {//두 Count 객체를 합하는 메소드
            return new Count(zero+other.zero,one+other.one);
        }
    }



    private Count count(int offsetX,int offsetY,int size,int[][] arr){
        int h=size/2; //4등분할 크기
        for(int y=offsetY;y<offsetY+size;y++){
            for(int x=offsetX;x<offsetX+size;x++){
                if(arr[y][x]!=arr[offsetY][offsetX]){ //영역안의 모든 원소가 같은 값이 아닌 경우
                    return count(offsetX,offsetY,h,arr) //반환형이 Count라 이렇게 add 메서드를 사용할 수 있음
                            .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) //모두 1인 경우
            return new Count(0,1);

        return new Count(1,0); //모두 0인 경우
    }

    public int[] solution(int[][] arr){
        Count count=count(0,0,arr.length,arr);
        return new int[]{count.zero,count.one};
    }
}

 

Count 객체를 만들지 않고 전역변수로 1과 0을 그냥 세도 됨.