[프로그래머스] 쿼드압축 후 개수 세기 - Java

문제 설명

 

프로그래머스

 

접근 방법

해당 문제는 재귀 함수를 이용하여 해결할 수 있었습니다.

 

최초 정사각형 배열 arr이 주어질 때, 각 요소가 다음과 같다고 가정해보겠습니다.

 

 

현재의 배열에서는 1의 개수는 9개, 0의 개수는 7개로 압축이 불가능합니다. 따라서 행과 열을 절반씩 나눠서 4개의 영역으로 재탐색합니다.

 

 

1번, 3번, 4번 영역은 앞선 탐색과 마찬가지로 하나의 수로 일치하지 않아 압축이 불가능하여 다시 각 영역별로 행과 열을 절반씩 나눠서 4개의 영역으로 탐색해야합니다. 반면, 2번 영역은 0이라는 수로 일치하기 때문에 0이라는 수로 압축이 가능하며 탐색을 종료하도록 합니다.

 

이처럼 일정한 패턴을 가지고 반복하여 탐색하는 과정은 재귀함수로 나타내기 용이합니다.

 

        // ...

        int length = arr.length;

        search(0, length, 0, length);

    }

    private void search(int rowStart, int rowEnd, int colStart, int colEnd) {
        // ...
    
        search(rowStart, (rowStart + rowEnd) / 2, colStart, (colStart + colEnd) / 2);
        search(rowStart, (rowStart + rowEnd) / 2, (colStart + colEnd) / 2, colEnd);
        search((rowStart + rowEnd) / 2, rowEnd, colStart, (colStart + colEnd) / 2);
        search((rowStart + rowEnd) / 2, rowEnd, (colStart + colEnd) / 2, colEnd);
    }

 

참고로 1번, 3번, 4번 영역의 경우 4개의 영역으로 쪼개져 하나의 요소만 남기 때문에 다음 탐색 시에는 반드시 특정 수로 압축되게 됩니다. 2번 영역은 현재 상태만으로도 압축이 되어 바로 탐색을 종료합니다.

 

재귀 탐색을 할 경우에는 반드시 종료 조건을 설정해주어야 합니다. 하지만 앞서 설정한 재귀 탐색 로직 상에는 종료 조건이 없었는데, 이러한 조건을 반영하여 다음과 같이 종료 조건을 설정해줄 수 있습니다.

 

    int[][] board;
    int countOfZero = 0, countOfOne = 0;
    
    // ...

    private void search(int rowStart, int rowEnd, int colStart, int colEnd) {
        int countOfZero = 0, countOfOne = 0;
        for (int i = rowStart; i < rowEnd; i++) {
            for (int j = colStart; j < colEnd; j++) {
                if (board[i][j] == 0) countOfZero++;
                else countOfOne++;
            }
        }

        if (countOfZero == 0) {
            this.countOfOne++;
        } else if (countOfOne == 0) {
            this.countOfZero++;
        } else {
            search(rowStart, (rowStart + rowEnd) / 2, colStart, (colStart + colEnd) / 2);
            search(rowStart, (rowStart + rowEnd) / 2, (colStart + colEnd) / 2, colEnd);
            search((rowStart + rowEnd) / 2, rowEnd, colStart, (colStart + colEnd) / 2);
            search((rowStart + rowEnd) / 2, rowEnd, (colStart + colEnd) / 2, colEnd);
        }
    }

 

여기서 종료 조건의 역할을 하는 것은 현재 영역의 '0'의 개수가 0개이거나 '1'의 개수가 0개인 경우 즉, 압축이되는 경우 또는 현재 영역의 요소가 단 1개밖에 존재하지 않는 경우입니다. 이 경우들에선 문제에서 요구하는 최종적으로 남은 0의 개수와 1의 개수를 각각 카운팅하고 (또다시 재귀되지 않고) 그대로 해당 메서드를 종료시키도록 합니다.

 

나의 소스 코드

class Solution {

    int[][] board;
    int countOfZero = 0, countOfOne = 0;

    public int[] solution(int[][] arr) {
        board = arr;
        int length = arr.length;

        search(0, length, 0, length);

        return new int[]{countOfZero, countOfOne};
    }

    private void search(int rowStart, int rowEnd, int colStart, int colEnd) {
        int countOfZero = 0, countOfOne = 0;
        for (int i = rowStart; i < rowEnd; i++) {
            for (int j = colStart; j < colEnd; j++) {
                if (board[i][j] == 0) countOfZero++;
                else countOfOne++;
            }
        }

        if (countOfZero == 0) {
            this.countOfOne++;
        } else if (countOfOne == 0) {
            this.countOfZero++;
        } else {
            search(rowStart, (rowStart + rowEnd) / 2, colStart, (colStart + colEnd) / 2);
            search(rowStart, (rowStart + rowEnd) / 2, (colStart + colEnd) / 2, colEnd);
            search((rowStart + rowEnd) / 2, rowEnd, colStart, (colStart + colEnd) / 2);
            search((rowStart + rowEnd) / 2, rowEnd, (colStart + colEnd) / 2, colEnd);
        }
    }
}

 

참고자료

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