Programmers - 쿼드압축 후 개수 세기 with JAVA

 

 

문제

2의 N승 X 2의 N승 크기의 배열이 주어지고 이 배열은 0 또는 1로 이루어진다. 이 때, 연속적으로 4만큼 배열을 나누어 해당 범위안에 모든 숫자가 같으면 묶을 수 있다. 묶게 된다면 해당 그룹은 모두 0 또는 1 하나로 묶인다. 이 때, 0의 개수와 1의 개수를 구하라.

 

 

 

로직

1. 초기 배열의 크기를 구한다.

2. 4등분 한다.

3. 4등분한 각 파트가 모두 0이거나 1인지 확인한다.

4. 3번이 참이라면 0 또는 1을 결과로 증가시킨다.

5. 3번이 거짓이라면 해당 범위를 다시 4로 나누어 반복한다.

 

추가적으로, 만약 초기 값이 모두 같은 값인지 처음에 체크해 같다면 0또는 1을 1개로해서 반환한다.

 

 

 

코드 1

class Solution {
    public static int[] answer = new int[2];
    public int[] solution(int[][] arr) {
        boolean conti = true;
        for(int x=0; x<arr.length; x++){
            for(int y=0; y<arr.length; y++){
                if(arr[x][y] != arr[0][0]){
                    conti = false;
                    break;
                }
            }
            if(!conti){
                break;
            }
        }
        if(conti){
            if(arr[0][0] == 0){
                answer[0] = 1;
                answer[1] = 0;
                return answer;
            }
            if(arr[0][0] == 1){
                answer[0] = 0;
                answer[1] = 1;
                return answer;
            }
        }
        int length = arr.length/2;
        for(int x=0; x<arr.length; x+=length){
            for(int y=0; y<arr.length; y+=length){
                find(x, y, length, arr);
            }
        }
        return answer;
    }
    public static void find(int now_x, int now_y, int length, int[][] arr){
        boolean conti = false;
        for(int x=now_x; x<now_x+length; x++){
            for(int y=now_y; y<now_y+length; y++){
                if(arr[x][y] != arr[now_x][now_y]){
                    conti = true;
                    break;
                }
            }
            if(conti){
                break;
            }
        }
        if(!conti){
            answer[arr[now_x][now_y]] += 1;
            return;
        }
        if(conti){
            for(int x=now_x; x<now_x+length; x+=length/2){
                for(int y=now_y; y<now_y+length; y+=length/2){
                    find(x, y, length/2, arr);   
                }
            }
        }
    }
}

 

 

코드 2

class Solution {
    public static int[] answer = new int[2];
    public int[] solution(int[][] arr) {
        int n = arr.length;
        while(true){
            for(int x=0; x<arr.length; x+=n){
                for(int y=0; y<arr.length; y+=n){
                    if(arr[x][y] != -1){
                        check(x, y, n, arr);   
                    }
                }
            }
            n /= 2;
            if(n == 0){
                break;
            }
        }
        return answer;
    }
    public static void check(int x, int y, int n, int[][] arr){
        boolean conti = true;
        for(int i=x; i<x+n; i++){
            for(int j=y; j<y+n; j++){
                if(arr[i][j] != arr[x][y]){
                    conti = false;
                    break;
                }
            }
        }
        if(conti){
            answer[arr[x][y]] += 1;
            for(int i=x; i<x+n; i++){
                for(int j=y; j<y+n; j++){
                    arr[i][j] = -1;
                }
            }
        }
    }
}