[Programmers] 쿼드압축 후 개수 세기

[문제 링크]

https://school.programmers.co.kr/learn/courses/30/lessons/68936

프로그래머스

 

[풀이 과정]

가장 큰 사각형부터 같은 숫자로 이루어져 있는지 검사를 하고
문제상 하나의 정사각형은 4개의 정삭각형으로 나눠질 수 있기 때문에
각각의 정사각형으로 쪼개지지 않거나 모두가 같은 수가 될 때까지 반복하여 답을 구합니다.

 

[코드]

import java.util.*;

class Solution {
    int[][] arr;
    int[] answer;
    
    public int[] solution(int[][] arr) {
        answer = new int[2];
        this.arr = arr;
        
        check(0, 0, arr.length);
        
        return answer;
    }
    
    public void check(int x, int y, int size) {
        if(isSame(x, y, size)) {
            answer[arr[x][y]]++;
            
            return;
        }
        
        // 같은 숫자가 아니면 4개의 영역으로 다시 나눔
        int half = size / 2;
        check(x, y, half); // 왼쪽 위
        check(x, y+half, half); // 오른쪽 위
        check(x+half, y, half); // 왼쪽 아래
        check(x+half, y+half, half); // 오른쪽 아래
    }
    
    public boolean isSame(int x, int y, int size) {
        int value = arr[x][y];
        
        for(int i = 0; i < size; i++) {
            for(int j = 0; j < size; j++) {
                if(arr[x + i][y + j] != value) {
                    return false;
                }
            }
        }
        return true;
    }
}

[회고]

40분정도 생각을 해봤지만 도저히 생각이 나지 않아 풀이과정을 보게 된 문제였습니다.

가장 작은 사각형부터 구해볼까?라는 바텀업 방색을 생각해 봤지만 탑다운 방식이었습니다.

새로운 유형이었습니다.
반복해서 풀어보며 익숙해져야겠습니다.

 

 

 

 

질문과 피드백은 언제나 환영입니다.

감사합니다.