[Lv.2] 쿼드압축 후 개수 세기 : Java

프로그래머스

 

 

 

이해하기

어려웠지만 스터디원분께서 설명해주신 덕분에 이해가 갔다!!

생각보다 예제 그대로인 문제...

 

위의 예시를 쿼드압축하려고 할 때 고려해야 할 순서는 다음과 같다.

 

1. 전부 같은 숫자인지 확인 

• 전부 0이면 answer[0]++
• 전부 1이면 answer[1]++

하지만 위의 예제는 전부 0 또는 1이 아니기에 4분할해서 다시 생각해보아야 한다.

 

2. 4분할된 면을 하나씩 살피며 다시 한 번 전부 같은 숫자인지 확인한다.

 

좌측상단은 전부 0 또는 1이 아니기에 다시 한 번 4분할해서 생각해야 한다.

4분할한 후에는 1개씩밖에 존재하지 않으므로 전부 1 또는 0 이라는 조건을 만족한다.

• answer[1]++ X 3회
• answer[0]++ X 1회

좌측상단은 끝!

 

그 다음 우측 상단은 전부 0이므로 한 번에 압축이 끝난다.

• answer[0]++ X 1회

 

좌측 하단도 좌측 상단과 마찬가지로 전부 0 또는 1이라는 조건을 만족하지 못하므로 다시 4분할한 후 살핀다.

4분할하면 각 1개씩만 있기에 조건을 만족한다.

• answer[1]++ X 3회
• answer[0]++ X 1회

 

우측 하단도 마찬가지로 다시 4분할한다.

• answer[1]++ X 3회
• answer[0]++ X 1회

이제 쿼드압축 및 개수 세기가 완료되었다.

한 번 이해하고 나니 개념은 숙지됐다!

 

 

문제풀이

class Solution {
    int[] answer = new int[2];

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

        quad(0, 0, size, arr);

        return answer;
    }

    public boolean isSame(int x, int y, int size, int[][] arr) {
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                if (arr[x][y] != arr[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

    public void quad(int x, int y, int size, int[][] arr) {
        if (isSame(x, y, size, arr)) {
            answer[arr[x][y]]++;
            return;
        }

        int half = size / 2;
        quad(x, y, half, arr);
        quad(x + half, y, half, arr);
        quad(x, y + half, half, arr);
        quad(x + half, y + half, half, arr);
    }
}

 

    int[] answer = new int[2];

 

answer[0]은 0의 개수, answer[1]은 1의 개수를 담을 것!

 

        int size = arr.length;

 

arr.length를 미리 size로 받아온다.

 

        quad(0, 0, size, arr);

 

quad에는 시작좌표인 (0, 0), 사이즈, arr 배열이 매개변수로 주어진다.

 

    public void quad(int x, int y, int size, int[][] arr) {
        if (isSame(x, y, size, arr)) {
            answer[arr[x][y]]++;
            return;
        }

 

quad 함수 내로 들어가면 가장 먼저 if문을 만나게 된다.

isSame 함수는 전체가 다 같은지를 가려내는 boolean 반환 함수이다.

만약 전체가 다 같은 숫자라면 여기에서 answer[arr[x][y]]++ 해준다.

arr[x][y]는 quad 함수에 주어진 탐색 시작 좌표로, 전체가 다 같다면 arr[x][y]의 값이 1 또는 0일테니 해당하는 answer[]를 ++ 해주는 것이다.

 

        int half = size / 2;
        quad(x, y, half, arr);
        quad(x + half, y, half, arr);
        quad(x, y + half, half, arr);
        quad(x + half, y + half, half, arr);

 

만약 전체가 다 같지 않다면 밑으로 내려와서 이 부분을 만나게 된다.

계산하기 쉽도록 half를 미리 계산해준다.

quad(x, y, half, arr); 는 좌측 상단 부분을 재탐색하도록 하고, quad(x + half, y, half, arr); 는 우측 상단, quad(x, y + half, half, arr); 는 좌측 하단, quad(x + half, y + half, half, arr); 는 우측 하단을 재탐색하도록 한다.

 

처음에 이 4가지 함수가 이해되지 않았는데 그림으로 그려보니 이해가 됐다!

 

 

 

 

 

사실 이 비슷한 문제를 제로베이스 코테에서 만났는데도 풀지 못했다는 점이 너무너무 아쉬웠다.

이번 기회에 쿼드압축 문제를 정복해버려야지...!