프로그래머스 - 쿼드압축 후 개수 세기

분할 정복 문제

 

1. 정사각형을 같은 크기로 4등분(길이 / 2)

2. 루프를 4번 돌려서 4등분한 길이만큼 정사각형 분할

3. 1~2 의 작업을 길이가 1이될 떄 까지 반복

4. 길이가 1일 때 현재의 원소 반환

5. 이렇게 분할된 값들을 모아서, 0과 1이 각각 몇 번 나왔는지 셈

6. 루프를 통해 0이나 1이 4번 나오면 적절히 처리해줌

7. 6번에서 0이 4번 나오면 0반환, 1이면 1 반환, 아니라면 2 반환

8. 5~7 반복

 

코드

class Solution {
    int[] answer = new int[2];
    public int[] solution(int[][] arr) {
        int ret;
        ret = divide(arr, arr.length, 0 ,0);
        // 모든 원소가 0이나 1인 경우 마지막에도 체크해야 함
        if(ret == 0)
            answer[0]++;
        else if(ret == 1)
            answer[1]++;
        return answer;
    }
    
    // 0 : 4개의 chunk가 모두 0
    // 1 : 4개의 chunk가 모두 1
    // 2 : 4개의 chunk에 0과 1이 섞인 경우 (아무 일도 없음)
    public int divide(int[][] arr, int n, int c, int r) {
        if(n == 1)
            return arr[c][r];
        int len = n / 2;
        int ret;
        // 4개의 chunk에 0과 1의 개수 셈
        int zero = 0, one = 0;
        //  정사각형 격자 
        for(int i=0; i<4; i++) {
            ret = divide(arr, len, c + (i / 2) * len, r + (i % 2) * len);
            if(ret == 0) {
                zero++;
                answer[0]++;
            }
                
            else if(ret == 1) {
                one++;
                answer[1]++;
            }    
        }
        // 정사각형의 4개의 chunk가 0일 때
        if(zero == 4) {
            answer[0] -= 4;
            return 0;
        }
        // 정사각형의 4개의 chunk가 1일 때
        else if(one == 4) {
            answer[1] -= 4;
            return 1;
        }
        // 그게 아니라면 그냥 리턴
        return 2;
    }
}

 

그림으로 설명하면 다음과 같다.

예시 1을 기준으로 배열을 다음과 같이 분할

 

첫 분할

이렇게 크기가 1 * 1이 될 때 까지 분할한다.

중간 분할

 

이제 결과를 합친다.

 

각 4개의 분할된 결과를 카운팅 해 주고, 특정 수가 4번 나오면 합친다.

여기서 합치는 것은 그냥 해당 숫자를 반환하는 것이고,

그 외는 아무 것도 아닌 숫자인 2를 반환시킨다.

 

중간 병합

 

 

위의 이미지에선 2만 0을 반환하고, 1, 3, 4는 아무것도 아닌 2를 반환한다.

이제 최종 병합 단계는 다음과 같다.

최종 병합

 

 

 

결과

 

 

각 분할에 대해 루프를 4번 돌면서 각 루프에 대해 행과 열 시작점만 정해주면 되는데

이걸 O(N^2)으로 푼 코드가 제일 위에 있길래 써봄