쿼드압축 후 개수 세기

Posted on Edited on In , ,

문제정의

정사각형의 0,1로 이루어진 2차원 배열을 압축하는 문제이다. 정사각형 영역 S가 한숫자로만 이루어져 있으면 그 숫자로 압축할 수 있다. 만약 그렇지 않으면 4개의 정사각형으로 나누어 압축할 수 있는지 확인한다. 이 과정을 반복했을 때 0의 개수와 1의 개수를 배열로 담아 반환하면 된다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
package level2;

public class QuadCompress {

    //프로그래머스 문제풀이 level2 쿼드압축 후 개수 세기
    public static void main(String[] args) {
        int[][] arr = {
            {1,1,0,0},
            {1,0,0,0},
            {1,0,0,1},
            {1,1,1,1}
        };
        int[] answer = new int[2];
        answer[0] = ReturnCnt(0, arr.length-1, 0, arr.length-1, arr, 0);
        answer[1] = ReturnCnt(0, arr.length-1, 0, arr.length-1, arr, 1);
    }
    public static int ReturnCnt(int start_r, int end_r, int start_c, int end_c, int[][] arr, int comp_num)
    {
        if(start_r == end_r)
            return arr[start_r][start_c] == comp_num ? 1 : 0;
        else
        {
            boolean canCompress = true;
            for(int r = start_r; r <= end_r; r++)
            {
                for(int c = start_c; c <= end_c; c++)
                {
                    if(arr[r][c] != comp_num)
                        canCompress = false;
                }
            }
            if(canCompress)
                return 1;
            
            int middle_r = (end_r-start_r)/2 + start_r;
            int middle_c = (end_c-start_c)/2 + start_c;
            int first = 0, sec = 0, third = 0, fourth = 0;
            first += ReturnCnt(start_r, middle_r, start_c, middle_c, arr, comp_num);
            sec += ReturnCnt(start_r, middle_r, middle_c+1, end_c, arr, comp_num);
            third += ReturnCnt(middle_r+1, end_r, start_c, middle_c, arr, comp_num);
            fourth += ReturnCnt(middle_r+1, end_r, middle_c+1, end_c, arr, comp_num);
            
            return first+sec+third+fourth;
            
            
            
        }    
        
    }
    
}
전형적인 리컬시브를 활요하는 문제이다. 필자는 0이나 1이 몇개인지 알려주는 함수 ReturnCnt를 만든 뒤, 0의 개수와 1의 개수를 각각 구하였다. 함수의 매개변수로는 사각형의 시작행과 열, 끝행과 열을 알기 위해 start_r, end_r, start_c, end_c로 선언했다. comp_num은 0 또는 1이 들어간다. 압축하는 숫자가 무엇인지 알려주는 역할이다. 리컬시브 함수가 종료되는 순간은 가로 세로가 1인 정사각형이 들어왔을 때이다. 첫행과 끝행이 같을 때가 이 경우 이므로, 이때 비교하는 수가 comp_num과 같으면 1을 그렇지 않으면 0을 반환한다. 다른 종료조건으로는 영역 전체가 comp_num으로 이루어진 경우이다. 이 조건은 2중 루프를 통해 파악한다. 이 모두가 아니라면 영역을 4개로 쪼개어 확인해야한다. 영역을 쪼개기 위해 정사각형을 쪼개는 가운데 점을 찾아야하는데 그건 35-36번째 줄을 참고하길 바란다. 이렇게 만들어진 중간열과 행을 middle_r과 middle_c로 선언한다. 다음에 자른 영역으로 함수를 재호출하여 4개의 영역값을 모두 더하여 반환한다.

시간복잡도에 대해 고민을 해보았는데, 최악의 경우는 단 하나도 압축이 안되는 경우이다. 일단 함수가 쪼개지는 횟수는 정사각형의 한 변의 길이를 \(n(n \ge 2)\)일 때, 등비수열의 합 공식에 의해 \(4*(4^n-1)\over(4-1)\)번이다. 쪼개진 영역들을 검사하는 횟수를 다 합하면 한번에 \(n^2\)이다. 따라서 총 시간복잡도는 \(O(n^2*4^n)\)이다.

테스트



이번 문제는 시간복잡도를 계산하는 것이 까다로웠다. 이제 재귀에 익숙해져 가는 것 같아 뿌듯하다.