[201106] 쿼드압축 후 개수 세기 - 월간 코드 챌린지 시즌1(level2)

0. 문제 유형 : Divide and Conquer(분할 정복)

1. 문제 이해

programmers.co.kr/learn/courses/30/lessons/68936

코딩테스트 연습 - 쿼드압축 후 개수 세기

(1) 주요 요구사항

- int[][] arr : 0과 1로 이루어진 2^n X 2^n 크기의 2차원 정수 배열 (1, 2, 4, ... , 1024)

- 쿼드 트리 방식으로 압축

1. 압축하고자 하는 특정 영역 = S
2. S 내부의 모든 수가 같은 값이면 해당 수 하나로 압축
3. 그렇지 않다면, S를 정확히 4개의 균일한 정사각형으로 쪼갠 뒤, 2와 같은 방식의 압축 시도(Divide & Conquer)

- 최종적으로 남는 0의 개수와 1의 개수를 return

 

(2) 주의할 사항(실수했던 것)

- 처음부터 0 혹은 1로 전부 채워진 사각형이라면 분할하여 확인할 필요가 없음

→ 문제에 주어진 플로우를 정확히 숙지하자!!!

- 2차원 배열의 indexing : x가 행, y가 열임을 잊지 말자!!

 

 

2. 전략

(1) 초기 arr가 쿼드 압축 조건에 만족하는지 확인

- 조건 체크를 위한 함수 checkQuard : 범위 내 모든 원소가 value와 같은 지 확인

(중첩 반복문 / value는 arr의 첫번째 값을 인수로 넣어준다.)

 

(2) 재귀 함수를 통한 Divide and Conquer

public void compression(int[][] arr, int x1, int y1, int x2, int y2)
[파라미터]
- int[][] arr : 주어진 2차원 정수 배열
- int x1, y1, x2, y2 : 확인할 범위의 왼쪽 위 좌표, 오른쪽 아래 좌표


[프로세스]
1. 4개의 영역으로 분할 
- unit : 두 기준 좌표를 가지고 분할될 사각형의 변의 길이 구함
- int[][] base : 4개 영역의 기준 좌표들을 담은 배열
{{x1, y1, x2-unit, y2-unit}, {x1, y1+unit, x2-unit, y2}, {x1+unit, y1, x2, y2-unit}, {x1+unit, y1+unit, x2, y2}}

2. 각 영역에 대해서 쿼드 압축 조건 확인
(1) 조건 만족 : 해당 수로  압축 (answer 배열)
(2) 조건 불만족 : compression 호출 (base배열에 의해 조정된 범위로)

 

 

3. 참고 사항

(1) 영역 분할의 기준

- 시작점(x1, y1)과 변의 길이(unit)으로 넘기는 방식도 있음 (출제자의 의도) : 변수가 차지하는 공간을 줄일 수 있음 & 간단

- 내 방법 : 중첩 for 문에서의 표현 간결성..??

 

(2) 시간복잡도 : O(n^2logn)

- 쿼드 압축 확인에 걸리는 시간 : 최악의 경우 n^2개의 원소에 대해서 확인  → O(n^2)

- 분할 횟수 : 최악의 경우 (1,1) 길이까지 분할 → O(logn)

▶ O(n^2logn)

cf> 프로그래머스 해설에 따르면 O(n^2)까지도 줄일 수 있다고 한다!! 고민해보자

prgms.tistory.com/32

 

 

4. 코드

class Solution {
    static int[] answer;
    public int[] solution(int[][] arr) {
        answer = new int[2];
        int size= arr.length-1;
        if(checkQuard(arr, 0, 0, size, size, arr[0][0]))    answer[arr[0][0]] += 1;
        else compression(arr, 0, 0, size, size);
        return answer;
    }
    
    public void compression(int[][] arr, int x1, int y1, int x2, int y2){
        int unit = (x2 - x1 + 1)/2;
        int[][] base = new int[][]{{x1, y1, x2-unit, y2-unit}, {x1, y1+unit, x2-unit, y2},
                                    {x1+unit, y1, x2, y2-unit}, {x1+unit, y1+unit, x2, y2}};
        for(int[] b : base){
            int initial = arr[b[0]][b[1]];
            boolean okay = checkQuard(arr, b[0], b[1], b[2], b[3], initial);
            if(okay)    answer[initial] += 1;
            else    compression(arr, b[0], b[1], b[2], b[3]);
        }
    }
    
    public boolean checkQuard(int[][] arr, int x1, int y1, int x2, int y2, int value){
        boolean okay = true;
        for(int i = x1; i <= x2; i++){
            for(int j = y1; j <= y2; j++){
                if(arr[i][j] != value){
                    okay = false; break;
                }
            }
        }
        return okay;
    }
}