[프로그래머스] 쿼드압축 후 개수 세기 (자바)

 📌 문제 소개

 

Level 2

 

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

프로그래머스

 

 

 

 🔍 문제 설명

 

0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.

1. 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
2. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
3. 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해 주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.

arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해 주세요.

 

 

제한 사항

arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다. 즉, arr의 행의 개수는 1, 2, 4, 8,..., 1024 중 하나입니다.

• arr의 각 행의 길이는 arr의 행의 개수와 같습니다. 즉, arr은 정사각형 배열입니다.
• arr의 각 행에 있는 모든 값은 0 또는 1입니다.

 

 📝 풀이 과정

 

이 문제는 재귀를 이용하면 어렵지 않게 해결할 수 있다. 한 사각형을 4 등분해서 처리하는 과정을 재귀로 구현하면 되는데, 각 호출마다 새로운 사격형의 (0,0) 위치의 초기 좌표를 넘겨받는 것이 중요하다. 이 초기 좌표를 이용해서 상대 좌표를 구현할 수 있는데, 이로 인해 사각형 안의 새로 호출된 임의의 사각형의 범위를 판단해서 정확하게 처리할 수 있다. 풀이과정은 다음과 같다.

 

 

1. 배열에 있는 값이 모두 0이거나 1인지 체크

본격적으로 4 등분하는 재귀 메서드를 작성하기 전에, 배열에 있는 값이 모두 0이거나 1일 경우를 생각해봐야 한다. 작성하는 재귀 메서드는 먼저 등분을 시켜놓고 배열을 순회하기 때문에, 4등분 된 값이 모두 같은 값이어도 즉시 종료되지 못하고 새로운 재귀 메서드를 호출한다. 따라서, 최초로 재귀 메서드를 호출하기 전에 배열을 순회해서 전부 0이거나 1일 경우 재귀 메서드를 호출하지 않고 즉시 종료하도록 코드를 작성해둬야 한다.

 

2. 초기 좌표, 배열, 크기를 매개변수로 받는 재귀 메서드 선언

여기서 말하는 초기 좌표는 사각형의 왼쪽 위의 좌표이고, 2차원 배열의 (0,0) 위치의 좌표를 말한다. 이 초기좌표를 이용하면, 만약 크기가 2*2인 사각형일 경우, 초기 좌표가 (0,0) 일 때, 왼쪽 위 사각형의 시작 좌표는 (0,0), 오른쪽 위 사각형의 시작 좌표는 (0,1), 왼쪽 아래 사각형의 시작좌표는 (1,0), 오른쪽 아래 사각형의 시작좌표는 (1,1)이 된다. 크기가 클 때도 이와 같은 방식으로 작성하면 된다.

 

3. 초기 좌표를 이용해서 사각형 4 등분하기

방금 말한 방식으로 사각형을 4등분으로 나눈 뒤, 배열을 순회해서 값이 모두 같으면 그 값이 0 또는 1인지 판별해서 zero 또는 one 변수의 값을 증가시키고, 값이 다르면 새롭게 재귀 메서드를 호출한다.

 

4. 더 이상 나눠질 수 없을 경우, 값 넘겨받고 종료시키기

2*2 크기의 사각형이 호출되었을 경우 더 이상 나눠질 수 없으므로 매개변수로 넘겨받은 size 값이 2일 때, 이 사각형 안에 있는 4개의 값을 확인해서 zero, one 변수의 값을 증가시켜야 한다. 

 

 

 

 🛎️ 정답 코드

 

class Solution {
    static int zero, one, temp;
    
    public int[] solution(int[][] arr) {
        
        // 모두 1이거나 0일 경우
        temp = arr[0][0];
        A : for (int i=0; i<arr.length; i++) {
            for (int k=0; k<arr[0].length; k++) {
                if (temp != arr[i][k]) {
                    break A;
                } else if (i==arr.length-1 && k==arr[0].length-1) {
                    if (temp == 0) {
                        return new int[] {1, 0};
                    } else {
                        return new int[] {0, 1};
                    }
                }
            }
        }
        
        divide(0, 0, arr, arr.length);
        
        return new int[] {zero, one};
    }
    
    static void divide(int startX, int startY, int[][] arr, int size) {
        
        // 사각형을 더 이상 나눌 수 없는 경우
        if (size == 2) {
            for (int i=startY; i<=startY+1; i++) {
                for (int k=startX; k<=startX+1; k++) {
                    if (arr[i][k]==0) {
                        zero++;
                    } else {
                        one++;
                    }
                }
            }
            return;
        }
        
        // 왼쪽 위
        temp = arr[startY][startX];
        
        A : for (int i=startY; i<startY+size/2; i++) {
            for (int k=startX; k<startX+size/2; k++) {
                
                if (temp != arr[i][k]) {
                    divide(startX, startY, arr, size/2);
                    break A;
                    
                } else if (i==(startY+size/2)-1 && k==(startX+size/2)-1) {
                    if (temp == 0) {
                        zero++;
                    } else {
                        one++;
                    }
                }
            }
        }
        
        // 오른쪽 위
        temp = arr[startY][startX+size/2];
        
        A : for (int i=startY; i<startY+size/2; i++) {
            for (int k=startX+size/2; k<startX+size; k++) {
                
                if (temp != arr[i][k]) {
                    divide(startX+size/2, startY, arr, size/2);
                    break A;
                    
                } else if (i==(startY+size/2)-1 && k==startX+size-1) {
                    if (temp == 0) {
                        zero++;
                    } else {
                        one++;
                    }
                }
            }
        }
        
        // 왼쪽 아래
        temp = arr[startY+size/2][startX];
        
        A : for (int i=startY+size/2; i<startY+size; i++) {
            for (int k=startX; k<startX+size/2; k++) {
                
                if (temp != arr[i][k]) {
                    divide(startX, startY+size/2, arr, size/2);
                    break A;
                    
                } else if (i==startY+size-1 && k==(startX+size/2)-1) {
                    if (temp == 0) {
                        zero++;
                    } else {
                        one++;
                    }
                }
            }
        }
        
        // 오른쪽 아래
        temp = arr[startY+size/2][startX+size/2];
        
        A : for (int i=startY+size/2; i<startY+size; i++) {
            for (int k=startX+size/2; k<startX+size; k++) {
                
                if (temp != arr[i][k]) {
                    divide(startX+size/2, startY+size/2, arr, size/2);
                    break A;
                    
                } else if (i==(startY+size)-1 && k==(startX+size)-1) {
                    if (temp == 0) {
                        zero++;
                    } else {
                        one++;
                    }
                }
            }
        }
    }
}