[프로그래머스] Lv.2 쿼드압축 후 개수 세기

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

프로그래머스

 

 

1. 전체 사각형을 4개로 나눈다.
2. 해당 사각형에서 모든 값이 같은 경우 해당 값으로 합축한다.
3. 4개로 나눈 후에, 또 나눌 수 있다면 분리한다.
4. 더 이상 나눌 수 없는 경우에 0과 1의 개수를 카운팅 한다.

 

문제를 보면, 각 4가지 영역에 대해서 값이 같은지 다른지 체크를 해야하기 때문에 재귀가 먼저 떠올랐다. 하지만, 그 다음에 막혔던 부분이 시작점 설정을 어떻게 해줄 것인가? 였다.

 

각 사분면의 시작점

그림으로 표현한다면 이렇게 될 것이다.

 

만약에 (0,0)에서 시작하지 않고 다른 지점에서 시작한다고 했을 땐 (x,y)로 치환만 해주면 된다!

 

이제 각 사분면들을 압축하고 순회하면서 모두 같은 값이라면 압축하여 배열에 저장하고, 아니라면 다음 탐색을 진행하면 된다. 코드로 만들어보자

class Solution {
    static int [] answer = new int[2];
    public int[] solution(int[][] arr) {
        int len = arr.length;
        
        compact(arr, 0, 0, len);
        return answer;
    }
    
    private void compact(int [][] arr, int x, int y, int size) {
        if (check(arr, x, y, size)) { // 압축했을 때 해당 값이 모두 동일하다면, answer 배열 값을 증가시켜준다.
            answer[arr[x][y]]++;
            return; 
        }
        int newSize = size / 2;
        compact(arr, x, y, newSize);  // 좌상단
        compact(arr, x, y + newSize, newSize);  // 우상단
        compact(arr, x + newSize, y, newSize);  // 좌하단
        compact(arr, x + newSize, y + newSize, newSize);  // 우하단
    }
    
    private boolean check(int [][] arr, int x, int y, int size) {
        for(int i = x; i < x + size; i++){
            for(int j = y; j < y + size; j++) {
                if (arr[x][y] != arr[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}

 

문제 풀이 회고

 

재귀에 익숙하지 않아 답을 봤는데도 감이 잘 오지 않았다.

 

우선 첫번째로, 계속 stackoverflow 에러가 발생했는데 재귀문의 종료조건인 return을 빼먹어서 발생헀고, 또 사각형의 범위를 줄여가면서 재귀를 돌려야 하는데 나는 길이를 줄이지 않고 size를 파라미터로 넣었다.

 

두가지 이유 때문에 stackoverflow가 발생했었다.

 

재귀를 이해하기 위해선

1. 종료 조건 설정

2. 어떻게 하면 잘게 나눌 수 있을지

 

두가지를 고려해서 풀어야겠다