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

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

코딩테스트 연습 - 쿼드압축 후 개수 세기

 

[ 풀이 ] 

 

1. S 내부가 하나의 수로 압축이 될 수 있는지 확인한다. S 내에서 배열 내의 원소를 모두 비교하는데, 하나라도 다른 값이 나오면 압축되지 못하는 경우이다.

// n : S의 가로, 세로 크기 , x_start , y_start : S의 행,열 시작점
static boolean isCorrect( int[][] arr , int x_start , int y_start , int n ){
    for( int i = x_start ; i < x_start + n ; i++ ){
        for( int j = y_start ; j < y_start + n ; j++ ){
            if( arr[i][j] != arr[x_start][y_start] ) return false;
        }
    }
    return true;
}

 

2. S 내부가 하나의 수로 압축이 된다면 1 또는 0 의 개수를 증가시킨다.

static void countUp( int[][] arr , int x , int y ){
    if( arr[x][y] == 0 ) zero_count++; 
    else if( arr[x][y] == 1 ) one_count++; 
}

 

3. S 내부가 하나의 수로 압축되지 못한다면 S의 크기 n 을 반으로 줄인 n / 2 에 대해서 다음 4가지 경우에 대해 조건 1 ~ 2 번을 다시 따져봐야 한다.

quad(arr, x_start , y_start , n / 2 );
quad(arr, x_start + n / 2, y_start , n / 2 );
quad(arr, x_start , y_start + n / 2 , n / 2 );
quad(arr, x_start + n / 2 , y_start + n / 2, n / 2 );

4. S의 크기 n 이 1이 될 때 까지 재귀를 반복한다.

[ quad() ]

static void quad( int[][] arr , int x_start , int y_start , int n ){
    if( n == 1 ){	// S의 가로,세로 길이가 1 이되면 더 이상 쪼갤 수 없음.
        countUp( arr , x_start , y_start );
        return;
    }
    
    // S가 압축될 수 있는지 확인
    if( isCorrect( arr, x_start , y_start , n ) ){
        countUp( arr , x_start , y_start );
        return;
    }        
    
    // 재귀
    quad(arr, x_start , y_start , n / 2 );
    quad(arr, x_start + n / 2, y_start , n / 2 );
    quad(arr, x_start , y_start + n / 2 , n / 2 );
    quad(arr, x_start + n / 2 , y_start + n / 2, n / 2 );
}

 

[ 전체 코드 ] 

class Solution {
    static int zero_count = 0;	// 0의 개수
    static int one_count = 0;	// 1의 개수
    public int[] solution(int[][] arr) {
        int[] answer = new int[2];
        quad( arr, 0 , 0 , arr.length );
        answer[0] = zero_count;
        answer[1] = one_count;
        return answer;
    }
    static void quad( int[][] arr , int x_start , int y_start , int n ){
        if( n == 1 ){	// S의 가로,세로 길이가 1 이되면 더 이상 쪼갤 수 없음.
            countUp( arr , x_start , y_start );
            return;
        }

        // S가 압축될 수 있는지 확인
        if( isCorrect( arr, x_start , y_start , n ) ){
            countUp( arr , x_start , y_start );
            return;
        }        

        // 재귀
        quad(arr, x_start , y_start , n / 2 );
        quad(arr, x_start + n / 2, y_start , n / 2 );
        quad(arr, x_start , y_start + n / 2 , n / 2 );
        quad(arr, x_start + n / 2 , y_start + n / 2, n / 2 );
    }
    
    // S가 압축될 수 있는지 확인하는 함수.
    // n : S의 가로, 세로 크기 , x_start , y_start : S의 행,열 시작점
    static boolean isCorrect( int[][] arr , int x_start , int y_start , int n ){    
        for( int i = x_start ; i < x_start + n ; i++ ){
            for( int j = y_start ; j < y_start + n ; j++ ){
                if( arr[i][j] != arr[x_start][y_start] ) return false;
            }
        }
        return true;
    }  
    static void countUp( int[][] arr , int x , int y ){
        if( arr[x][y] == 0 ) zero_count++; 
        else if( arr[x][y] == 1 ) one_count++; 
    }
}