[Java] 프로그래머스 - 쿼드압축 후 개수 세기(lv.2)

기존 코드

import java.util.*;

class Solution {
    private int zeroCnt;
    private int oneCnt;
    private int[][] sqr;

    public int[] solution(int[][] arr) {
        sqr = arr;
        dnq(0, sqr.length, 0, sqr.length);

        return new int[]{zeroCnt, oneCnt};
    }

    private void dnq(int rs, int re, int cs, int ce){
        //열의 시작 좌표와 끝 좌표, 행의 시작 좌표와 끝 좌표를 뺀값이 1보다 작거나 같을 때 종료
        //근데 size로 계산하는게 더 간편하고 단순해보임
        if(re-rs<=1||ce-cs<=1){
            if(sqr[rs][cs] == 0){
                zeroCnt++;
                return;
            }
            oneCnt++;

            return;
        }       
            //s가 같은 숫자일 때 리턴
            if(isSameNumber(rs, re, cs, ce)){
                if(sqr[rs][cs] == 0){
                    zeroCnt++;
                    return;
                }
                oneCnt++;
                return;
            }

            //하나의 블럭이 아니면 4개로 분할
            //제 1사분면
            dnq(rs, re/2, ce/2, ce);
            //제 2사분면
            dnq(rs, re/2, cs, ce/2);
            //제 3사분면
            dnq(re/2, re, cs, ce/2);
            //제 4사분면
            dnq(re/2, re, ce/2, ce);

    }

    private boolean isSameNumber(int rs, int re, int cs, int ce){
        for(int i=rs; i<re; i++){
            for(int j=cs; j<ce; j++){
                if(sqr[rs][cs]!=sqr[i][j]){
                    return false;
                }   
            }
        }
        return true;
    }
}

개선 후 코드

import java.util.*;

class Solution {
    private int zeroCnt;
    private int oneCnt;
    private int[][] sqr;

    public int[] solution(int[][] arr) {
        sqr = arr;
        dnq(0, 0, sqr.length);

        return new int[]{zeroCnt, oneCnt};
    }

    private void dnq(int rowStart, int colStart, int size) {
        //열의 시작 좌표와 끝 좌표, 행의 시작 좌표와 끝 좌표를 뺀값이 1보다 작거나 같을 때 종료
        //근데 size로 계산하는게 더 간편하고 단순해보임
        if(size==1){
            if(sqr[rowStart][colStart] == 0){
                zeroCnt++;
                return;
            }
            oneCnt++;
            return;
        }       
            //s가 같은 숫자일 때 리턴
            if(isSameNumber(rowStart, colStart, size)){
                if(sqr[rowStart][colStart] == 0){
                    zeroCnt++;
                    return;
                }
                oneCnt++;
                return;
            }

            //하나의 블럭이 아니면 4개로 분할
            //제 1사분면
            dnq(rowStart, colStart+size/2, size/2);
            //제 2사분면
            dnq(rowStart, colStart, size/2);
            //제 3사분면
            dnq(rowStart + size/2, colStart, size/2);
            //제 4사분면
            dnq(rowStart + size/2, colStart + size/2, size/2);

    }

    private boolean isSameNumber(int rowStart, int colStart, int size){
        for(int i=rowStart; i<rowStart+size; i++){
            for(int j=colStart; j<colStart+size; j++){
                if(sqr[rowStart][colStart]!=sqr[i][j]){
                    return false;
                }   
            }
        }
        return true;
    }
}

행의 시작과 끝 좌표, 열의 시작과 끝 좌표를 재귀함수의 매개변수로 보내던 것에서
행의 시작 좌표, 열의 시작 좌표, 분할된 배열의 사이즈(길이)를 매개변수로 보내도록 수정했다.

이렇게 함으로써 얻게된 점 은 제 1사분면 ~ 제 4사분면의 좌표를 계산할 때 훨씬 복잡하지 않게 됐다는 점과 좌표를 계산할 때 엣지케이스가 발생하지 않았다는 점이다.

정리하자면 처음에 문제를 풀지 못했던 이유는 제 n사분면의 좌표를 구할 때 행과 열의 시작좌표와 끝 좌표를 모두 받았고 이를 통해서 분할 이후 좌표까지 계산했기 때문에 너무 복잡해졌다는 점, 그리고 좌표계산이 맞지 않게되는 상황도 발생했기 때문이다.

구글링을 통해 행(열)의 시작좌표와 현재 배열의 사이즈만 보내는 아이디어를 발견했고 이를 적용해 훨씬 쉽게 해결할 수 있었다.

분할정복: 행의 시작 좌표, 열의 시작 좌표, 현재 배열의 사이즈를 재귀함수로 보내면 대부분 쉽게 풀어진다.

---

2024.1.29 풀이

class Solution {
    private int zeroCnt;
    private int oneCnt;

    public int[] solution(int[][] arr) {
        int N = calcLog(arr.length);
        int res = dnq(arr, N, 0, 0);

        //2차원 배열 전부 같은 숫자인 경우 카운팅
        if(res==0){
            zeroCnt++;
        }else if(res==1){
            oneCnt++;
        }

        return new int[]{zeroCnt, oneCnt}; 
    }

    //재귀
    private int dnq(int[][] arr, int n, int startR, int startC){
        if(n==0){
            return arr[startR][startC];
        }
        int[] res = new int[4];
        res[0] = dnq(arr, n-1, startR, startC); // 제 2사분면
        res[1] = dnq(arr, n-1, startR, startC+(int)Math.pow(2, n-1)); //제 1사분면
        res[2] = dnq(arr, n-1, startR+(int)Math.pow(2, n-1), startC); //제 3사분면
        res[3] = dnq(arr, n-1, startR+(int)Math.pow(2, n-1), startC+(int)Math.pow(2, n-1)); //제 4사분면

        //네 번의 dnq리턴값이 전부 같은 값이면 해당 값 리턴
        if(res[0]==res[1]&&res[0]==res[2]&&res[0]==res[3]){
            return res[0];
        }

        //다른 값이면 cnt후 -1 리턴
        for(int i=0; i<4; i++){
            if(res[i]==0){
                zeroCnt++;
                continue;
            }
            if(res[i]==1){
                oneCnt++;
            }
        }
        return -1;   
    }

    private int calcLog(int arrLength){
        return (int)(Math.log10((double)arrLength)/Math.log10(2.0));
    }
}

재귀 함수가 int값을 리턴하도록 구현했고, 재귀함수의 매개변수로 제곱수를 받도록 했다.
하지만 위 개선 후 코드에서와 같이 void타입으로 구현하고 재귀함수 호출 시 Math.pow함수의 활용이 아닌 나누기 연산을 활용한다면 가독성도 복잡도도 줄어드는 코드가 됐을 것이다.

위 코드에선 재귀함수가 제곱수를 매개변수로 받음에 따라 arr의 length가 2의 몇 제곱인지 계산하는 메서드를 만들었다.
java에서는 밑이 10인 로그를 계산하는 메서드를 제공하기에 이를 로그의 밑 변환 공식에 적용하여 구할 수 있었다.