월간 코드 챌린지 시즌1 > 쿼드압축 후 개수 세기 - JAVA (분할 정복)

 

 

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

프로그래머스

 

 

풀이 - 나의 생각

제목이 거창하지만

 

결국에는 분할 정복입니다.

 

 

분할 정복은

 

조건에 부합하지 않을 경우 탐색 범위를 줄여가면서

 

조건을 부합하는 경우를 찾아가는 겁니다.

 

그렇기 때문에

 

우선 위의 그림처럼

 

처음에 2차원 배열을 값들을 한 번 살펴봅니다.

 

그랬을때 모든 값이 같으면 그 값으로 압축하면 끝

 

하지만 다른 값이 있으면 4등분하고 다시 검색하는 겁니다.

 

저 같은 경우

 

메소드를 하나 만들어 살펴볼 범위와 좌표 값을 넘깁니다.

 

그러면 그 좌표의 값을 기준으로 두고

 

넘겨 받은 범위를 둘러봅니다.

 

모든 값이 같다면 끝

 

아니라면 분할해서 다시 분석하도록 요청합니다.

 

1번째 탐색 후 분할 후 탐색하기

 

위의 그림을 보면 처음에는 배열의 크기 8만큼을(Size = 8)

 

arr[0][0]부터(x = 0, y = 0) 탐색을 합니다.

 

그런데 arr[1][0] == 0 이기에 분할 후 탐색을 해야합니다.

 

그렇기에 size 를 절반으로 나눈후(4를 나누는게 아닙니다.)

 

적절한 탐색 위치를 지정해주면 됩니다.

 

그 적절한 탐색 위치는

 

x, x + size, y, y + size를 적적히 조합하면 구할 수 있습니다

 

코드

 

import java.util.*;

class Solution {
    static int[][] map;
    static int[] answer;
    public int[] solution(int[][] arr) {
        answer = new int[2];
        map = Arrays.copyOf(arr, arr.length);
        divide(arr.length, 0, 0);
        return answer;
    }
    
    public static void divide(int size, int x, int y){
        int num = map[x][y];
        boolean flag = true;
        for(int i = x; i < x+size; i++){
            for(int j = y; j < y+size; j++){
                if(num != map[i][j]){
                    flag = false;
                    break;
                }
            }
        }
        if(flag){
            answer[num]++;
        }else{
            size/=2;
            divide(size, x, y);
            divide(size, x+size, y);
            divide(size, x, y+size);
            divide(size, x+size, y+size);
        }
    }
}

 

 

 

 

 

 

 

다음에 또 봐요