(Java)프로그래머스 코딩테스트 연습 - 월간 코드 챌린지 시즌1 - 쿼드압축 후 개수 세기

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/68936?language=java

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

2. 나의 풀이

class Solution {
    public int[] solution(int[][] arr) {
        int[] answer = {0, 0};
    	answer = check(0, arr.length, 0, arr[0].length, arr, answer);
        return answer;
    }
    
    int [] check(int start_i, int end_i, int start_j, int end_j, int [][] arr, int [] answer) {
    	//System.out.println("i : " + start_i + " ~ " + end_i + ", j : " + start_j + " ~ " + end_j);
    	//for(int i = start_i; i < end_i; i = i + 1) {
    	//	for(int j = start_j; j < end_j; j = j + 1) {
    	//		System.out.print(arr[i][j]);
    	//	}
    	//	System.out.println("");
    	//}
    	int imsi = arr[start_i][start_j];
    	boolean right = true;
    	if(end_i - start_i == 1) {
    		
    	}else {
    		loop:
    		for(int i = start_i; i < end_i; i = i + 1) {
    			for(int j = start_j; j < end_j; j = j + 1) {
    				if(imsi != arr[i][j]) {
    					right = false;
    					break loop;
    				}
    			}
    		}
    	}
    	//배열이 동일한 경우 그 수를 확인하여 answer에 0일 경우 0번 인덱스에 1추가 1일 경우 1번 인덱스에 1추가
    	if(right == true) {
    		if(imsi == 0) {
    			answer[0] += 1;
    		}else if(imsi == 1) {
    			answer[1] += 1;
    		}
    		//System.out.println("answer : " + Arrays.toString(answer));
    	//배열이 동일하지 않을 경우 4등분하여 재귀
    	}else if(right == false) {
    		//좌상단 1/4 부분
    		answer = check(start_i, (start_i + end_i) / 2, start_j, (start_j + end_j) / 2, arr, answer);
    		//좌하단 1/4 부분
    		answer = check((start_i + end_i) / 2, end_i, start_j, (start_j + end_j) / 2, arr, answer);
    		//우상단 1/4 부분
    		answer = check(start_i, (start_i + end_i) / 2, (start_j + end_j) / 2, end_j, arr, answer);
    		//우하단 1/4 부분
    		answer = check((start_i + end_i) / 2, end_i, (start_j + end_j) / 2, end_j, arr, answer);
    		
    	}
    	return answer;
    }
}

3. 다른 사람 풀이

import java.util.*;

class Solution {
    static int[] answer;
    private static int m;

    public static void main(String[] args) {
        System.out.println(Arrays.toString(solution(new int[][]{{1, 1, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 1}, {1, 1, 1, 1}})));
    }

    public static int[] solution(int[][] arr) {
        answer = new int[2];
        int n = arr.length;

        divide(0, 0, n, arr);

        return answer;
    }

    private static boolean check(int row, int col, int n, int[][] map) {
        int std = map[row][col];
        for (int i = row; i < row + n; i++) {
            for (int j = col; j < col + n; j++) {
                if (std != map[i][j]) {
                    return false;
                }
            }
        }
        m = std;
        return true;
    }

    private static void divide(int row, int col, int n, int[][] map) {
        if (check(row, col, n, map)) {
            if (m == 0)
                answer[0]++;
            else
                answer[1]++;
        } else {
            int s = n / 2;
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 2; j++) {
                    divide(row + s * i, col + s * j, s, map);
                }
            }
        }
    }
}