프로그래머스 (C/C++, Java) 68936 : 쿼드압축 후 개수 세기

 

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

프로그래머스

 

---

풀이

주어진 배열을 탐색하다가 셀 내에 모든 값이 같지 않다면 현재 배열을 4등분한다.

이 때 나눠진 배열의 크기와 시작 좌표를 같이 넘겨 작은 단위의 배열을 탐색하며, 이를 재귀로 반복한다.

만약 모든 값이 같다면 현재 셀의 공통적인 값의 개수를 증가시킨다.

---

C/C++ 코드

#include <string>
#include <vector>

using namespace std;

vector<int> answer(2, 0);

void compress(vector<vector<int>>& arr, int sr, int sc, int n) {
    int val = arr[sr][sc];
    for (int i = sr; i < sr + n; i++) {
        for (int j = sc; j < sc + n; j++) {
            if (val != arr[i][j]) {
                n /= 2;
                compress(arr, sr, sc, n);
                compress(arr, sr, sc + n, n);
                compress(arr, sr + n, sc, n);
                compress(arr, sr + n, sc + n, n);
                return;
            }
        }
    }
    answer[val]++;
}

vector<int> solution(vector<vector<int>> arr) {
    int n = arr.size();
    compress(arr, 0, 0, n);
    return answer;
}

 

Java 코드

class Solution {
    private int[] answer = {0, 0};
    public int[] solution(int[][] arr) {
        int n = arr.length;
        
        compress(arr, 0, 0, n);
        return answer;
    }
    
    private void compress(int[][] arr, int sr, int sc, int n) {
        int value = arr[sr][sc];
        for (int i = sr; i < sr + n; i++) {
            for (int j = sc; j < sc + n; j++) {
                if (arr[i][j] != value) {
                    n /= 2;
                    compress(arr, sr, sc, n);
                    compress(arr, sr, sc + n, n);
                    compress(arr, sr + n, sc, n);
                    compress(arr, sr + n, sc + n, n);
                    return;
                }
            }
        }
        
        answer[value]++;
    }
}