[ Programmers - LV2 ] 쿼드압축 후 개수 세기

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

프로그래머스

분할 정복 문제로 기본 문제로 연습하기에 딱 좋은 문제인 것 같다.

스터디에서 선정한 문제인데 스터디원들 각자 풀이를 봤을 때 백트래킹 / DFS 같이 다양한 알고리즘으로 분류 되었는데, 결국 핵심은 재귀적으로 더 이상 작은 범위로 좁혀지지 않을 때 까지 쪼개는게 문제의 핵심이다.

---

[ 📌 분석 ]

크게 분석에 시간을 많이 쓸 필요 없었던게 문제가 원하는 명확했다.

[ 8 x 8 ]

2^3 으로 주어진 8 x 8 사이즈 크기의 배열이라면 위와 같이 맨 처음에는 전체 배열을 검사하고 배열의 모든 수가 같은 수(0 혹은 1)로 이루어지지 않았다면 다음 스텝을 진행한다.

[ 4 x 4 ]

1 ~ 4 분면까지 나누어서 다음 스텝을 진행하면 되는데, 재귀적으로 탐색 한다는 이유는 4 x 4 사이즈로 나누어 졌을 때 1 사분면 부터 4 사분면 까지 전부 검사하는게 아니라 1 사분면을 확인하고, 조건을 만족하지 않으면 다시 1 사분면을 나눠서 4개로 만들기를 반복해서 조건에 만족할 때 까지 반복한다.

[ 1 x 1 ]

결국 마지막으로 가면 1 x 1 사이즈가 되고, 이 사이즈는 나눌 수 있는 최소 사이즈로 구성하는 요소의 값이 단 하나일 수 밖에 없으니 조건을 만족한다.

---

[ 📌 연습 ]

오랜만에 풀이하는 유형의 문제여서 문제를 풀기 전에 나는 가볍게 연습삼아서 코드를 작성했다.

public class Temp {
    public static void main(String[] args) {
        int[][] arr = new int[][] {
                { 0, 1,   2,  3,  4,  5,  6,  7},
                { 8, 9,  10, 11, 12, 13, 14, 15},
                {16, 17, 18, 19, 20, 21, 22, 23},
                {24, 25, 26, 27, 28, 29, 30, 31},
                {32, 33, 34, 35, 36, 37, 38, 39},
                {40, 41, 42, 43, 44, 45, 46, 47},
                {48, 49, 50, 51, 52, 53, 54, 55},
                {56, 57, 58, 59, 60, 61, 62, 63},
        };

        for(int i = 0; i < 5; i+=4) {
            for(int j = 0; j < 5; j+=4) {
                test(arr, i, j, 4);
            }
        }
    }

    public static void test(int[][] arr, int srtX, int srtY, int tmp) {
        if(tmp == 1) return;
        System.out.println(srtX + " " + srtY + " " + tmp + " !!!");

        for(int i = srtX; i < srtX + tmp; i++) {
            for(int j = srtY; j < srtY + tmp; j++) {
                System.out.print(arr[i][j] + " ");
            }
        }
        System.out.println();
        System.out.println("############################");

        tmp /= 2;

        for(int i = srtX; i <= srtX + tmp; i+=tmp) {
            for(int j = srtY; j <= srtY + tmp; j+=tmp) {
                test(arr, i, j, tmp);
            }
        }
    }
}

 

위 코드를 실행한 결과로는 아래 처럼 쪼개지는 과정이 나온다.

0 1 2 3 8 9 10 11 16 17 18 19 24 25 26 27 
############################
0 0 2 !!!
0 1 8 9 
############################
0 2 2 !!!
2 3 10 11 
############################
2 0 2 !!!
16 17 24 25 
############################
2 2 2 !!!
18 19 26 27 
...

 

8 x 8 사이즈로 고정하고, 하드 코딩과 함께 진행 했지만, 본질은 큰 것을 작게 나눠서 작은 범위로 들어가는 것이다.

---

[ 📌 코드 - Java ]

class Solution {

    int[] answer = {0, 0};  // 0, 1 의 합

    public int[] solution(int[][] arr) {
        dividAndSum(arr, 0, 0, arr.length);

        return answer;
    }

    public void dividAndSum(int[][] arr, int x, int y, int size) {
        boolean isMergeable = true;

        LOOP:
        for(int i = x; i < x + size; i++) {
            for(int j = y; j < y + size; j++) {
                if(arr[x][y] != arr[i][j]) {
                    isMergeable = false;
                    break LOOP;
                }
            }
        }

        if(isMergeable) {
            answer[arr[x][y]]++;
            return;
        }

        if(size == 1) return;

        size /= 2;

        dividAndSum(arr, x, y, size);
        dividAndSum(arr, x, (y + size), size);
        dividAndSum(arr, (x + size), y, size);
        dividAndSum(arr, (x + size), (y + size), size);

    }
}

 

처음 풀이에서는 나눈 그룹이 0 과 1 로 이루어져 있는지 확인하는 2 중 루프에서 다름을 확인하고도 break 를 하지 않았었는데, 추가 해주니 성능적인 개선이 있었다.

 

필요 없는 연산은 최대한 안하도록 지향하자!!!