728x90
https://programmers.co.kr/learn/courses/30/lessons/68936
코딩테스트 연습 - 쿼드압축 후 개수 세기
[[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] [4,9] [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] [10,15]
programmers.co.kr
문제 풀이
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 )
반응형