[프로그래머스] Lv. 2 쿼드압축 후 개수 세기(Java)

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

프로그래머스

 

정답 코드

class Solution {
    
    private static class Count {
        public final int zero;
        public final int one;
        
        public Count(final int zero, final int one) {
            this.zero = zero;
            this.one = one;
        }
        
        public Count add(final Count other) {
            return new Count(zero + other.zero, one + other.one);
        }
        
    }
    
    private Count count(final int offsetX, final int offsetY, final int size, final int[][] arr) {
        int h = size / 2;
        for (int x = offsetX; x < offsetX + size; x++) {
            for (int y = offsetY; y < offsetY + size; y++) {
                if (arr[y][x] != arr[offsetY][offsetX]) {
                    return count(offsetX, offsetY, h, arr)
                        .add(count(offsetX + h, offsetY, h, arr))
                        .add(count(offsetX, offsetY + h, h, arr))
                        .add(count(offsetX + h, offsetY + h, h, arr));
                }
            }
        }
        
        if (arr[offsetY][offsetX] == 1) {
            return new Count(0, 1);
        }
        return new Count(1, 0);
    }
    
    public int[] solution(final int[][] arr) {
        final Count count = count(0, 0, arr.length, arr);
        return new int[] {count.zero, count.one};
    }
    
}

 

설명

2차원 배열을 탐색하며 특정 조건을 만족하는 영역을 찾는 문제는

분할 정복(Divide and Conquer) 방식으로 해결할 수 있다.

 

이번 문제에서는 배열을 4등분하여 재귀적으로 탐색하면서

0과 1의 개수를 구하는 방법을 설명한다.

 

1. 배열의 시작 위치(offsetX, offsetY)와 크기(size)를 기준으로 해당 영역을 탐색한다.
2. 반복문을 통해 해당 영역의 모든 값을 확인하고, 기준 값과 다른 값이 있는지 검사한다.
3. 모든 값이 같으면 현재 영역의 값(0 또는 1)을 반환한다.
4. 값이 섞여 있다면 배열을 4 등분하여 각 영역에 대해 재귀 호출을 수행한다.
5. 각 영역의 결과를 합산하여 최종 결과로 반환한다.

 

실행 결과

 

참고 자료 :

취업과 이직을 위한 프로그래머스 코딩 테스트 문제 풀이 전략 : 자바 편 | 김현이

프로그래머스 코딩 테스트 문제 풀이 전략: 자바 편 | 김현이 - 교보문고