[programmers] 쿼드압축 후 개수 세기 (Java)

[쿼드압축 후 개수 세기]

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

프로그래머스

 

[접근 방법]

쿼드 압축을 구현하는 방식으로 '재귀호출' 을 이용하는 것을 선택하였다.

쿼드 압축이 가능하기 위해서는 범위 내 모든 원소의 값이 0 또는 1로 동일해야 한다.

그를 판단하기 위한 메서드 (zip) 를 구현한다.

쿼드 압축 함수 (quadTree) 는 zip 을 조건문의 판단문으로 사용하여, 압축이 가능하다면,

1이면, answer[1]++ 로

0이면, answer[0]++ 으로 한다.

 

압축이 가능할때 까지 4분할을 하여 재귀호출을 진행한다.

 

[Java 코드]

import java.util.*;

class Solution {

    static int[] answer;

    /**
     * 쿼드 압축이 가능한지 확인하는 메서드
     * @param arr : arr
     * @param x : x 시작점
     * @param y : y 시작점
     * @param size : 영역 사이즈
     * @param val : 값
     * @return
     */
    public boolean zip(int[][] arr, int x, int y, int size, int val) {
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                if (arr[i][j] != val) {
                    return false;
                }
            }
        }

        return true;
    }

    public void quadTree(int[][] arr, int x, int y, int size) {
        if (zip(arr, x, y, size, arr[x][y])) {
            if (arr[x][y] == 1) {
                answer[1] ++;
            } else {
                answer[0] ++;
            }
            return;
        }

        //재귀형식으로 4등분하여 탐색
        quadTree(arr, x, y, size/2);
        quadTree(arr, x, y + size/2, size/2);
        quadTree(arr, x + size/2, y, size/2);
        quadTree(arr, x + size/2, y + size/2, size/2);
    }


    public int[] solution(int[][] arr) {
        answer = new int[2];
        quadTree(arr, 0, 0, arr.length);
        return answer;
    }
}

 

[Rewind]

1. 어려웠던 점

'재귀 호출'을 이용해야 한다 라는 것을 알고 있었지만, 구체적으로 어떻게 구현해야 하는지 알지 못했다.

 

2. 알게된 점

재귀 호출로 문제를 해결하는 한가지 방법을 알게 되었다.

 

3. 개선방안

여러 문제를 통해 방법을 습득하는 것이 필요하다.