[프로그래머스,Java] Levle2: 쿼드 압축 후 개수 세기

 

문제분석

 

문제 목표:  0과 1로 이루어진 배열이 주어집니다. 

1.만약 모든배열이 0 또는 1로 전부 채워져있으면 압축합니다.

2.전부 채워져있지않으면, 배열을 4등분한뒤 1번을 반복합니다.

 

0과 1의 갯수를 구해주세요.

 

 

그림을보면 계속 4등분하는 로직을 '반복'하는걸 주목하셔야합니다.

무슨 알고리즘을 써야하는지 감이 오셧겟지만,  재귀함수를 사용해야합니다.

 

 

코드를 보면서 문제에대한 접근을 설명하겟습니다.

 

우선 메인함수와 전역변수입니다.

 

전역변수의 zero 와 one은 각각 0의 갯수와 1의 갯수입니다.

rec();를 호출하고 zero와 one의 갯수를 세줍니다.

 

그래서 rec()를 보시자면

 

 

문제를 읽어보시면 

1.먼저 1또는 0으로 배열이 모두 채워졋는데 확인한다.

 

2.만약 모두채워지지않았다면 4등분한뒤 다시 1를 반복한다. 딱 그걸 한겁니다.

 

2중반복문으로 0또는 1로 모두 채워졋는지 확인합니다.

만약, 0또는 1로 채워져있지않으면  flag=false로 만들고 2중반복문을 끊어줍니다.

이미 압축이불가능한데 굳이 모든 배열을 더 확인할필요가 없잖아요?

 

만약 flag가 true , 압축이가능한상태면  배열의 원소하나를 (0또는 1) 더해주고 재귀 종료.

 

만약 flag가 false 라면 배열을 4등분해서 반복시킵니다.

 

P.s 재귀함수를 다룰수 있는지 물어보는 아주 Level2다운 문제입니다.

재귀함수 연습문제용으로 딱이라고 생각합니다.

문제풀이

 

class Solution {   
int zero=0;
int one=0;
    public int[] solution(int[][] arr) {       
        rec(arr,arr.length,0,0);
        int[] answer = new int[]{zero,one};
        return answer;
    } 
    public void rec(int[][] arr, int len,int x, int y){      
        boolean flag=false;
  Loop:   for(int i=y;i<y+len;i++){
            for(int j=x;j<x+len;j++){
                if(arr[i][j]==arr[y][x]){
                    flag=true;                 
                }
                else{
                    flag=false;
                    break Loop;
                }            
            }
        }
        if(flag){
            if(arr[y][x]==0) zero++;
            if(arr[y][x]==1) one++;    
            return;
        }          
        rec(arr,len/2,x,y);    
        rec(arr,len/2,x+len/2,y);
        rec(arr,len/2,x,y+len/2);
        rec(arr,len/2,x+len/2,y+len/2);  
    }
}