[프로그래머스 월간 코드 챌린지 시즌1] 쿼드압축 후 개수 세기 -Java

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

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

class Solution {
	    public int[] solution(int[][] arr) {
	        int[] answer = new int[2];
	        
	        solve(answer, arr,0,0,arr.length, arr.length,arr.length);
	        return answer;
	    }
	    
	    public void solve(int []answer, int [][]arr,int sx,int sy,int ex,int ey, int n){
	        int num=arr[sx][sy];
	        int cnt=0;
	        for(int i=sx; i<ex; i++){
	            for(int j=sy; j<ey; j++){
	                if(arr[i][j]!=num){ //다르다면 놔눠서 다시 부르기
	                	solve(answer, arr, sx,sy,sx+n/2, sy+n/2, n/2);
	                	solve(answer, arr, sx,sy+n/2,sx+n/2, sy+n, n/2);
	                	solve(answer, arr, sx+n/2,sy,sx+n, sy+n/2, n/2);
	                	solve(answer, arr, sx+n/2,sy+n/2,sx+n, sy+n, n/2);
	                	return ;
	                }
	                else cnt++;
	            }
	        }
	        
	        if(cnt==n*n) answer[num]++;
	        
	    }
	}

소요시간 : 25분

 

대표적인 분할정복 문제입니다.

 

로직을 살펴보면 

 

1. 현재의 사각형의 요소가 모두 같은지 확인한다.

2. 만약 모두 같다면 해당하는 요소의 배열 인덱스를 ++해준다.

3. 만약 하나라도 다른게 있다면 현재 배열을 4등분해서 1번으로 돌아간다.

 

 

재귀를 통해서 이런식으로 다른 요소가 있다면 배열의 인덱스를 고쳐서 다시 1번로직부터 실행하면 됩니다.

 

끝~