[프로그래머스(Programmers)][자바(java)] (Lv2) 쿼드압축 후 개수 세기 <월간 코드 챌린지 시즌1>

 

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

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

 

문제 풀이

 

class Solution {

	int zero, one;
	
	public void DivConq( int a[][], int x, int y, int len ) {
		if( len == 0 )
			return;
		boolean isDiff = false;
		for( int i = x; i < x+len; i++ ) {
			for( int j = y; j < y+len; j++ ) {
				if( a[x][y] != a[i][j] ) {
					isDiff = true;
					break;
				}
			}
 		}
		if( isDiff ) {
			DivConq( a, x, y, len/2 );
			DivConq( a, x, y+len/2, len/2 );
			DivConq( a, x+len/2, y, len/2 );
			DivConq( a, x+len/2, y+len/2, len/2 );
		}
		else {
			if( a[x][y] == 0 )	zero++;
			else				one++;
		}
	}
	
	public int[] solution(int[][] arr) {
		int n = arr.length;
		DivConq( arr, 0, 0, n );
		return new int[] { zero, one };
	}
}

 

*  분할정복 ( 재귀 + 같은 크기로 분할 )

-  0, 1 각각의 개수를 카운트 할 변수( zero, one ) 선언  ( 클래스 변수에 선언하여 자동으로 0으로 초기화 )
-  재귀함수에 입력받은 2차원 배열 ( int arr[][] ), 압축할 영역의 시작점 ( x, y ), 압축할 영역의 길이 ( len )을 전달
-  시작점 ( x, y ) 으로부터 크기가 len*len인 정사각형 영역을 루프로 탐색
-  시작점의 값( a[x][y] )과 현재 값( a[i][j] )이 다르면 같은 값으로 압축이 불가능하므로 4 영역으로 쪼갬

x	y	len
x	y	len/2
x	y + len/2	len/2
x + len/2	y	len/2
x + len/2	y + len/2	len/2

-  영역 안의 모든 값이 같으면 압축이 가능하므로 탐색을 종료하고 그 값을 카운트하는 변수( zero or one )에 개수를 증가시킴
-  재귀 함수는 len이 0이 되면 종료시킴 ( base case )