프로그래머스 - 쿼드압축 후 개수 세기 (JAVA, 자바)

문제 링크

문제 설명

0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.

1. 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
2. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
3. 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.

arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

---

제한사항

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

---

입출력 예

arr	result
[[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]]	[4,9]
[[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]]	[10,15]

---

입출력 예 설명

입출력 예 #1

• 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.
• 
• 최종 압축 결과에 0이 4개, 1이 9개 있으므로, [4,9]를 return 해야 합니다.

입출력 예 #2

• 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.
• 
• 최종 압축 결과에 0이 10개, 1이 15개 있으므로, [10,15]를 return 해야 합니다.

문제 풀이 방법

이문제의 핵심 포인트는 배열을 나눈다는 점이다.

1. 재귀방법으로 문제를 풀이 한다.
2. 배열을 쪼갠다.
3. 탐색할 배열 시작 범위의 x, y 좌표와 크기를 변수로 넘긴다.
4. 나눠진 사각형에서 값을 확인 한다.

처음에 문제를 접했을 때 재귀방법으로 접근해야한다는 점은 바로 알았지만 재귀에서 넘겨줘야하는 변수를 정하는게 어려웠다.
해당 변수만 정하면 쉽게 해결 되는 문제이다.

4 X 4 배열을 보면 위에 사진처럼 해당 좌표를 가진다.

이 배열을 압축을 해보면 사진 처럼 사이즈가 2인 정사각형이 4개로 나눠진다.

이 사각형에서 시작 지점을 표시해보면 빨간색으로 표시된 위치가 각 사각형의 시작 지점이 된다.
이 좌표를 수식화 하면 1 ➡️ x, y 2 ➡️ x, y + size 3 ➡️ x + size, y 4 ➡️ x + size, y + size 가 된다.

이렇게 나눠진 사각형에서 값이 같은지 체크한 뒤 answer 값을 하나씩 증가 시키면 된다.

코드에서 answer[arr[a][b]]++; 이렇게 표시한 이유는 arr[a][b] 값이 0 이면 answer[0] 의 값을 하나 증가 시키는 것이고, arr[a][b] 값이 1 이면 answer[1] 의 값이 증가 된다.

---

전체 코드

class Solution {
    public static int[] answer;
    public int[] solution(int[][] arr) {
        answer = new int[2];
        divide(arr, 0, 0, arr.length);
        return answer;
    }
    
    public static void divide(int[][] arr, int a, int b, int size){

        if(check(arr, a, b, size)){
            answer[arr[a][b]]++;
            return;
        }

        divide(arr, a, b, size /2); // 1
        divide(arr, a, b + size / 2, size / 2 ); // 2
        divide(arr, a + size / 2, b, size / 2 ); // 3
        divide(arr, a + size / 2, b + size / 2, size / 2 ); // 4
    }

    public static boolean check(int[][]arr, int a, int b, int size){
        for (int i = a; i < a + size ; i++) {
            for (int j = b; j < b +size ; j++) {
                if(arr[a][b] != arr[i][j]){
                    return false;
                }
            }
        }
        return true;
    }
}