(Python, Java) 프로그래머스 - 쿼드압축 후 개수 세기

26 Jan 2022 in Algorithm on Programmers, Level2

[문제 링크]

Python 풀이

def solution(arr):
    answer = [0, 0]

    def check(size, x, y):
        if size == 1:
            answer[arr[x][y]] += 1
            return

        target = arr[x][y]

        for px in range(size):
            for py in range(size):
                # 일치 하지 않으면 쪼개기
                if target != arr[x + px][y + py]:
                    resize = size // 2
                    check(resize, x, y)
                    check(resize, x + resize, y + resize)
                    check(resize, x + resize, y)
                    check(resize, x, y + resize)
                    return
        # 일치하면 해당에 +1
        answer[target] += 1

    check(len(arr), 0, 0)
    return answer

Java 풀이

class Solution {

    int[] answer;
    int[][] board;

    public int[] solution(int[][] arr) {
        answer = new int[2];
        board = arr;

        check(arr.length, 0, 0);
        return answer;
    }

    private void check(int size, int x, int y) {
        if (size == 1) {
            answer[board[x][y]] += 1;
            return;
        }

        int target = board[x][y];
        for (int dx = 0; dx < size; dx++) {
            for (int dy = 0; dy < size; dy++) {
                if (board[x + dx][y + dy] != target) {
                    int resize = size / 2;
                    check(resize, x, y);
                    check(resize, x + resize, y);
                    check(resize, x, y + resize);
                    check(resize, x + resize, y + resize);
                    return;
                }
            }
        }
        answer[target] += 1;
    }
}