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

쿼드압축 후 개수 세기

문제 설명

1. 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.

2. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.

3. 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.

제한사항

• arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다. 즉, arr의 행의 개수는 1, 2, 4, 8, ..., 1024 중 하나입니다.
• arr의 각 행의 길이는 arr의 행의 개수와 같습니다. 즉, arr은 정사각형 배열입니다.
• arr의 각 행에 있는 모든 값은 0 또는 1 입니다.

입출력 예

입출력 예 설명

• 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.

• 최종 압축 결과에 0이 4개, 1이 9개 있으므로, [4,9]를 return 해야 합니다.

• 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.

• 최종 압축 결과에 0이 10개, 1이 15개 있으므로, [10,15]를 return 해야 합니다.

solution.java

class Solution {
    public int[] solution(int[][] arr) {
        // 압축 후 0과 1의 카운트 저장
        int[] result = new int[2];
        compressHelper(arr, 0, 0, arr.length, result);
        return result;
    }
    
    // 압축을 재귀적으로 수행하는 함수
    private void compressHelper(int[][] arr, int x, int y, int size, int[] result) {
        if (isUniform(arr, x, y, size)) {
            // 모든 요소가 동일한 경우 해당 숫자의 카운트 증가
            if (arr[x][y] == 0) {
                result[0]++;
            } else {
                result[1]++;
            }
        } else {
            // 그렇지 않으면 현재 영역을 4개의 작은 하위 영역으로 나누기
            int newSize = size / 2;
            compressHelper(arr, x, y, newSize, result); // 좌상단
            compressHelper(arr, x, y + newSize, newSize, result); // 우상단
            compressHelper(arr, x + newSize, y, newSize, result); // 좌하단
            compressHelper(arr, x + newSize, y + newSize, newSize, result); // 우하단
        }
    }
    
    // 사각형 하위 행렬의 모든 요소가 동일한지 확인하는 함수
    private boolean isUniform(int[][] arr, int x, int y, int size) {
        int firstValue = arr[x][y];
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                if (arr[i][j] != firstValue) {
                    return false;
                }
            }
        }
        return true;
    }
}

핵심 키워드

• 재귀함수를 이용해 가장 큰 사각형부터 1x1 크기의 사각형까지 영역을 나눈다.
• 사각형 하위 행렬의 모든 요소가 동일한지 확인한후, 동일하다면 카운트를 증가시킨다.
• 동일하지 않다면 사이즈를 /2씩 감소시킨 후, 계속해서 모든 요소가 동일한지 확인한다.

결론!