[Java] [월간 코드 챌린지 시즌1] Lv2.쿼드압축 후 개수 세기

문제는 어렵지 않았다.

쿼드를 나누고, 해당 쿼드의 모든 숫자가 같은지 판단하고,

같지 않다면 반복하면 됐다.

 

문제를 풀면서, 하나 깨닫게 된 게 있는데

바로바로

중간값 산출이다!

 

여태까지는 두 인덱스 사이의 중간값을 구하라고 하면 (끝 값 - 첫 값)/2로 구했는데,

첫 값과 끝값이 정말로 전체 인덱스의 첫 값과 끝 값이 아닌 경우라면, 이런 방법으로 구하면 안됐다.

 

예시를 들어보자면,

인덱스가 4, 5, 6, 7, 8 일 경우, 중간 인덱스를 구해보자

• 이전 방식 : (8 - 4) / 2 = 2
• 올바른 방식 : (4 + 8) / 2 = 6

 정확하게 두 인덱스 사이의 중간 인덱스 값을 구하려면 두 값을 더해서 2로 나누어야 한다

 

 

class Solution {
    int[][] arr;
    int[] answer = new int[2];
    public int[] solution(int[][] arr) {
        this.arr = arr;
        int n = arr.length; // 길이
        
        getQuad(0, n, 0, n);
        
        return answer;
    }
    
    void getQuad(int sx, int ex, int sy, int ey){
        // 최후, 1*1 크기의 쿼드 도착
        if(ex - sx == 1 && ey - ex == 1){
            if(arr[sx][sy] == 0) answer[0] += 1;
            else answer[1] += 1;
            return;
        }
        
        int cur_num = arr[sx][sy];
        boolean flag = true;
        
        for(int i = sx; i < ex; i++){
            for(int j = sy; j < ey; j++){
                if(arr[i][j] != cur_num){
                    flag = false;
                    break;
                }
            }
        }
        
        if(!flag){
            int midX = (sx+ex) / 2;
            int midY = (sy+ey) / 2;
            
            getQuad(sx, midX, sy, midY);
            getQuad(midX, ex, sy, midY);
            getQuad(sx, midX, midY, ey);
            getQuad(midX, ex, midY, ey);  
        }else{
            if(arr[sx][sy] == 0){
                answer[0] += 1;
            }
            else{
                answer[1] += 1;
            }
        }
    }
}