[프로그래머스] 쿼드압축 후 개수 세기(68936)

1. 문제 풀이 아이디어

• 2차원 배열을 4등분하여 재귀적으로 처리하면 문제를 해결할 수 있다.

2. 나의 정답 코드

class Solution {
    private int[][] arr;
    private final int[] result = new int[2];

    public int[] solution(int[][] arr) {
        this.arr = arr;
        solve(0, 0, arr.length);

        return result;
    }

    private int solve(int x, int y, int size) {
        if (size == 1) {
            result[arr[x][y]]++;
            return arr[x][y];
        }
        int a = solve(x, y, size / 2);
        int b = solve(x + size / 2, y, size / 2);
        int c = solve(x, y + size / 2, size / 2);
        int d = solve(x + size / 2, y + size / 2, size / 2);
        if (a != 2 && a == b && b == c && c == d) {
            result[a] -= 3;
            return a;
        }
        return 2;
    }
}

3. 정리

• 주어진 배열을 4등분하며 처리하는 solve 메서드를 구현한다.

• solve 메서드는 4등분한 배열의 값이 모두 0 또는 1로 동일할 경우, 해당 값을 반환하고, 다를 경우 2를 반환한다.

• size가 1인 경우, 해당 위치의 값에 따라 결과 배열을 증가시킨 뒤, 그 값을 반환한다.

• 4등분한 값이 2가 아니고 모두 동일하다면 하나로 압축할 수 있으므로, 해당 값의 개수를 3만큼 감소시킨 후 반환한다.

• 모든 재귀 호출이 완료되면, result 배열에는 0과 1의 개수가 저장되어 문제를 해결할 수 있다.