쿼드압축 후 개수 세기

링크텍스트

문제 설명

1. 길이가 2의 배수인 배열을 정사각형 형태로 쪼갰을 때 그 안에 있는 숫자가 모두 같은 숫자라면 해당 숫자로 통일
2. 다른 숫자라면 길이가 1이 될 때까지 쪼개면서 통일시키기
   2-1. 길이가 1이 된다면 나 자신이므로 무조건 같은 숫자임

시행착오 및 풀이 방법

정답 풀이

1. 재귀함수로 길이를 반으로 나누면서 각 사각형이 가지고 있는 숫자 찾기
   1-1. 이중 for문으로 다 같은 숫자라면 true, 하나라도 아닌게 있다면 false 반환
2. 0과 1의 갯수를 구하는 문제이므로 answer[0]++과 answer[1]++을 해준다.

정답 코드

//1. 같은 숫자인지 판별하는 함수
//2. 아니라면 더 쪼개는 함수
import java.util.*;
class Solution {
    static int[] answer = new int[2];
    public int[] solution(int[][] arr) {

        //사각형 쪼개기
        recursive(0,0,arr.length,arr);
        
        return answer;
    }
    
    public void recursive(int x, int y, int size, int[][] arr) {
        //다 같은 숫자라면 해당 숫자 +1
        if(check(x, y, size, arr)) {
            answer[arr[x][y]]++;
        }
        //아니라면 재귀함수를 통해 사각형 쪼개기
        else {
            //왼쪽 위
            recursive(x, y, size/2, arr);
            //오른쪽 위
            recursive(x+size/2, y, size/2, arr);
            //왼쪽 아래
            recursive(x, y+size/2, size/2, arr);
            //오른쪽 아래
            recursive(x+size/2, y+size/2, size/2, arr);
            
        }
    }
    
    //숫자 판별
    public boolean check(int x, int y, int size, int[][] arr) {
        for(int i=x; i<x+size; i++) {
            for(int j=y; j<y+size; j++) {
                //같지 않다면 하나로 합칠 수 없음
                if(arr[i][j] != arr[x][y]) {
                    return false;
                }
            }
        }
        //다 같다면 하나로 합칠 수 있음
        return true;
    }
}

시행착오

시행착오.. 까지는 아니고

//다 같은 숫자라면 해당 숫자 +1
        if(check(x, y, size, arr)) {
            answer[arr[x][y]]++;
            return;
        }

예전에 풀었던 코드랑 차이점은 이 return이 있고 없고 차이다.
사쉴 이 return은 있으나 없으나다.
if절이 끝나고 나면 함수가 끝난것이기에 반환되는건 마찬가지여서!

암튼 이렇게 통과~!

그리고 answer[0]일 때랑 answer[1]일 때 어떻게 나눠서 +1을 해주지? 라는 고민을 잠깐 했었다.
그래서 첨엔 또 if절 써서 이게 0인지~ 1인지~ 구구절절하게 썼는데 생각해보니 0하고 1이여서 그냥 인덱스로 넣으면 됐었다 ^~^

---

재귀문제 나왔다 하면 일단 쫄고 시작한다...
쫄지마 쫄보 주연지~