[프로그래머스/Level2] 쿼드압축 후 개수 세기 (JAVA)

📖 문제

프로그래머스

 

💡  풀이 방식

• 재귀 (분할정복)

1. (0,0) 좌표에서부터 재귀를 시작한다.

2. 만약 해당 좌표에서 범위까지 있는 모든 수들이 같다면 압축이 가능하므로 압축하고, 0/1의 갯수에 +1한다. 압축이 불가능하다면, 4분할 재귀를 시작한다.

divide(x,          y,          size/2);
divide(x,          y + size/2, size/2);
divide(x + size/2, y,          size/2);
divide(x + size/2, y + size/2, size/2);

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static int[][] arr;
    static int[] answer = new int[2];
    
    public int[] solution(int[][] arr) {
        this.arr = arr;
        
        divide(0, 0, arr.length);        
        return answer;
    }
    
    private static void divide(int x, int y, int size) {
        if(zip(x, y, size)) {   // 압축 가능하면 압축
            if(arr[x][y] == 0)  answer[0]++;
            else                answer[1]++;
            
            return;
        }
        
        // 압축 못 하면 또 4등분 (재귀)
        divide(x,          y,          size/2);
        divide(x,          y + size/2, size/2);
        divide(x + size/2, y,          size/2);
        divide(x + size/2, y + size/2, size/2);
    }
    
    // 압축 가능한지 판별하는 메서드 (범위 내 값이 모두 같은지 확인)
    private static boolean zip(int x, int y, int size) {        
        for(int i = x ; i < x + size ; i++) {
            for(int j = y ; j < y + size ; j++) {
                if(arr[i][j] != arr[x][y])
                    return false;
            }
        }
        
        return true;
    }
}

 

 

 

➕ 다른 풀이 방식

- 격자 크기가 1이 될 때까지 재귀 함수 돌리는 방법 (내가 풀고 싶었던 방법이다)

class Solution {
    static int[][] arr;
    static int[] answer = new int[2];
    
    public int[] solution(int[][] arr) {
    	this.arr = arr;
        
        int num = square(0, 0, arr.length);
        
        if (num != -1) {
            answer[num]++;
        }
        return answer;
    }
    
    private static int square(int x, int y, int size) {
        if (size == 1) {
            return arr[x][y];
        }
        
        int[] quarter = new int[4];
        quarter[0] = square(x, y, size / 2);
        quarter[1] = square(x, y + size / 2, size / 2);
        quarter[2] = square(x + size / 2, y, size / 2);
        quarter[3] = square(x + size / 2, y + size / 2, size / 2);
        
        if (quarter[0] != -1 && quarter[0] == quarter[1] && quarter[0] == quarter[2] && quarter[0] == quarter[3]) {
            return quarter[0];
        }
        
        for (int i = 0; i < 4; i++) {
            if (quarter[i] == -1) {
                continue;
            }
            answer[quarter[i]]++;
        }
        
        return -1;
    }
}

---

💦 어려웠던 점

- 재귀도 생각했고, 4분할 메소드 저렇게 할 생각도 했는데 재귀 종료 조건을 제대로 생각하지 못 했다.

- 재귀 파라미터에 길이를 넣을 생각은 하지 못 했다.

- 그리고 size가 1일 때 재귀 함수를 종료하는 방식으로 진행할 생각을 했었다.

 

 

🧐 새로 알게 된 내용

- 4분할 압축 방법 → 압축할 길이를 재귀 함수의 파라미터로 들고 다니기

- 잊고 있던 분할 정복....재귀를 잊지 마,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

프로그래머스 쿼드압축 후 개수 세기 (Java)

 

[프로그래머스] 쿼드압축 후 개수 세기 for JAVA 분할정복