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

# 문제

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 함수를 완성해주세요.

 

# 풀이 (자바) 

import java.util.Arrays;

class Solution {
    public static int[] answer; // [0,1]
    
    public static int check(int[][] arr, int x, int y, int n) {
        for (int i = x; i < x + n; i++) {
			for (int j = y; j < y + n; j++) {
				if (arr[i][j] != arr[x][y]) {return -1;}
			}
		}
        answer[arr[x][y]]++;
		return 0;
    }

	public static void compression(int[][] arr, int x, int y, int n) {
        if (n == 1) {
			if (arr[x][y] == 1) {answer[1]++;}
			else {answer[0]++;}
			return;
		}
		if(check(arr, x, y, n) == 0){return;}
        
		compression(arr, x ,y, n/2);
		compression(arr, x + n/2, y, n/2);
		compression(arr, x, y + n/2, n/2);
		compression(arr, x + n/2, y + n/2, n/2);
	}
	
	public static int[] solution(int[][] arr) {
        answer = new int[2];
        compression(arr, 0, 0, arr[0].length);
        return answer;
    }
}

 

#느낀점

재귀함수 (Recursive function) 을 통해 사용한 문제. 처음에는 check 메소드를 다음과 같이 했었다

 public static int check(int[][] arr, int x, int y, int n) {
        int count = 0;
		
		for (int i = x; i < x + len; i++) {
			for (int j = y; j < y + len; j++) {
				if (arr[i][j] == 1) {count++;}
			}
		}
		if (count == (int)Math.pow(2, len)) || count == 0) {
			answer[arr[i][j]]++;
			return 0;
		}  
		return -1;
	}

검증하는 박스 안에서 1의 개수를 담고,

전체 박스 안의 셀 개수 (2의 n승) 와 count 의 수가 같으면 전체가 1로 압축, count 가 0 이라면 전체가 0 으로 압축하는 방법으로 접근했는데, 예제 문제는 통과하고 몇 개의 테스트 케이스는 통과했지만 한 절반정도가 계속 통과가 안되더라 ㅠㅠ... 

왜 안되는 건지 하루종일 머리싸매고 고쳐보려했지만 이유는 결국 찾지 못했다...

if (arr[i][j] != arr[x][y]) {return -1;}

결국 위의 알고리즘으로 문제를 풀긴 했지만 원래 생각했던 방법으로는 풀지 못해 조금 찝찝하다...

 

 

아무튼 박스를 나누어 검증하는 알고리즘을 설명해보자면,

처음 int[][] 배열을 받았을 때 전체 셀을 검사 하고, 1또는 0로 압축이 불가능하다면 

 

compression 메소드안의 compression 메소드 (재귀함수) 를 통해 이렇게 1/4 을 검증하게 된다

compression 메소드는 총 4개가 사용되는데, 순서대로 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 검증되는 것이다. 

 

 

마지막까지 진행되어, 셀의 개수 (n) 가 1이 되었을 때 멈추게 된다.