카테고리: 재귀

문제

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

풀이 방식

1. 0과 1의 개수를 담을 Count 클래스를 생성한다.
2. 종료조건이 배열의 모든 원소가 같은 수일때로 잡고 재귀 메서드를 생성한다.
3. 종료조건에 부합할때까지 정사각형을 사등분하여 부분문제로 재귀 호출한다.

풀이 코드

import java.util.List;
import java.util.ArrayList;

class Solution {
    private static class Count{
        public final int zero, one;

        private Count(int zero, int one){
            this.zero = zero;
            this.one = one;
        }
    }

    private static int[][] splitArr(int[][] arr, int size, int start, int end){
        int[][] new_arr = new int[size][size];
        for(int i=0; i< size; i++){
            for(int j=0; j< size; j++){
                new_arr[i][j] = arr[start + i][end + j];
            }
        }

        return new_arr;
    }

    private static List<Count> compression(int[][] arr){
        List<Count> result = new ArrayList<>();
        int size = arr.length;// 정사각형 크기

        //종료조건 : 배열안의 모든 원소가 같은 수 일때
        int sum = 0;
        for(int[] row : arr){
            for(int a : row){
                sum += a;
            }
        }

        if(sum == 0){
            // 모든 원소가 0
            result.add(new Count(1,0));
        }else if(sum == size * size){
            // 모든 원소가 1
            result.add(new Count(0,1));
        }else {
            // 정사각형을 4등분한다
            int new_size = size / 2;

            //첫번째방
            result.addAll(compression(splitArr(arr, new_size, 0,0)));
            //두번째방
            result.addAll(compression(splitArr(arr, new_size, 0, new_size)));
            //세번째방
            result.addAll(compression(splitArr(arr, new_size, new_size, 0)));
            //네번째방
            result.addAll(compression(splitArr(arr, new_size, new_size, new_size)));
        }

        return result;
    }

    public int[] solution(int[][] arr) {
        List<Count> counts = compression(arr);

        int zero_total = 0;
        int one_total = 0;
        for(Count count : counts){
            zero_total += count.zero;
            one_total += count.one;
        }

        int[] answer = {zero_total,one_total};

        return answer;
    }
}