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

문제내용

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 입니다.

 

입출력 예 #1

• 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.

• 

• 최종 압축 결과에 0이 4개, 1이 9개 있으므로, [4,9]를 return 해야 합니다.

입출력 예 #2

• 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.

• 

• 최종 압축 결과에 0이 10개, 1이 15개 있으므로, [10,15]를 return 해야 합니다.

---

문제풀이

이전에 백준에서 비슷한 문제를 푼적이 있다. Divide & Conquer 를 활용한 알고리즘으로 뭐,,, BFS, 크루스칼, 플로이드, 다익스트라 등.. 이런 알고리즘처럼 어떤 식이 존재하는 알고리즘이 아니라 개념이다.

이문제를 풀때 중요한건 Divide 즉, 어떻게 나눌것인지 . 로직은 어떻게 짤것인지가 중요하다고 생각한다. 그리고 일반적으로 나눌때 재귀를 많이 활용하는걸로 알고 있고 필자도 이문제를 풀때 재귀를 이용해 풀었다.

 

예제에서 주어진 2차원 배열을 보면 다음과 같다.

1	1	0	0
1	0	0	0
1	0	0	1
1	1	1	1

이 배열을 빨간색, 보라색, 초록색, 노란색 4가지 부분으로 나누고, 다시 각각에 색에 대해서 같은수로 이루어져 있는지 파악해주면 된다.

 

빨간색의 경우

1	1
1	0

빨간색의 경우 4개의 수가 같은수가 아니므로 결국 다시 1, 1, 1, 0 으로 나누고 1과 0의 개수를 세면된다.

 

보라색의 경우

0	0
0	0

보라색의 경우 4개의 수가 0으로 같은 값인걸 알 수 있다. 따라서 이때는 0 하나로 볼 수 있다.

 

초록색의 경우

1	0
1	1

빨간색과 마찬가지의 경우이다.

 

노란색의 경우

0	1
1	1

빨간색, 초록색과 마찬가지의 경우이다.

 

즉, 문제에선 주어진 2차원 배열이 같은수로 이뤄져 있는지 확인하고, 4등분하고 , 확인하고 , 4등분하고 , 확인하고를 재귀를 통해 반복해주면 된다.

 

---

코드

public class Solution {
	static private int zero = 0;
	static private int one = 0;
    public int[] solution(int[][] arr) {
        int[] answer = new int[2];
        divide(arr);
        answer[0]=zero;
        answer[1]=one;
        return answer;
    }
    
    //배열 4등분 시키기
    public static void divide(int[][] arr) {
    	int check = arr[0][0];//가장 첫번째 수
    	boolean flag = true;//arr배열이 같은 수로 이뤄져있는지 체크하기위한 변수
    	
    	//같은수로 이뤄져있는지 확인하기
    	for(int i=0; i<arr.length; i++) {
    		for(int j=0; j<arr.length; j++) {
    			if(check!=arr[i][j]) {//다른수가 나왔을때.
    				flag = false;
    				break;
    			}
    		}
    	}
    	
    	//arr배열이 같은수라면
    	if(flag) {
    		if(check==1) {//그 숫자가 1이면 one 카운트하고 함수 종료
    			one++;
    			return;
    		}else if(check==0) {//숫자가 0이면 zero 카운트하고 함수 종료
    			zero++;
    			return;
    		}
    	}
    	
    	//4등분된 2차원배열을 담아줄 변수
    	int[][] sub = new int[arr.length/2][arr.length/2];
    	
    	//좌상단 배열만들기
    	for(int i=0; i<arr.length/2; i++) {
    		for(int j=0; j<arr.length/2; j++) {
    			sub[i][j]=arr[i][j];
    		}
    	}
    	divide(sub);//좌상단에 대해서 탐색
    	
    	//우상단 배열만들기
    	for(int i=0; i<arr.length/2; i++) {
    		for(int j=arr.length/2, b=0; j<arr.length; j++,b++) {
    			sub[i][b]=arr[i][j];
    		}
    	}
    	divide(sub);//우상단에 대해서 탐색
    	
    	//좌하단 배열만들기
    	for(int i=arr.length/2, a=0; i<arr.length; i++,a++) {
    		for(int j=0; j<arr.length/2; j++) {
    			sub[a][j]=arr[i][j];
    		}
    	}
    	divide(sub);//좌하단에 대해서 탐색
    	
    	//우하단 배열 만들기
    	for(int i=arr.length/2, a=0; i<arr.length; i++,a++) {
    		for(int j=arr.length/2, b=0; j<arr.length; j++,b++) {
    			sub[a][b]=arr[i][j];
    		}
    	}
    	divide(sub);//우하단에 대해서 탐색
    }
}

---

마치며

이전에 비슷한 문제를 풀어봤기 때문에 쉽게 접근이 가능했던 문제다. 앞에서 말했지만 문제에서 중요한건 어떻게 나눌것인지, 나누는 로직을 어떻게 짤 것인지가 중요하다고 본다.