[프로그래머스] 쿼드압축 후 개수 세기 for JAVA 분할정복

문제설명

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

 

입출력 예

arr	result
[[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]]	[4,9]
[[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]]	[10,15]

 

문제풀이

문제설명의 2, 3번을 통해 이 문제는 분할정복 문제임을 알 수 있다.

분할정복 문제는 아래 3단계 절차만 생각하면 쉽게 풀이할 수 있다.

 

1) 작은 영역으로 나누기
2) 나누어진 작은 영역 계산
3) 필요 시, 해결된 답 모으기

 

Step1

모든 수가 같은 값인지 확인하기 위해  check 함수를 구현한다. 모든 수가 같은 값이라면 True를, 다른 값이 하나라도 있다면 false를 return 한다.

	private static boolean check(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;
	}

 

Step2

실질적인 분할정복을 수행하는 함수인 dp이다. 시작지점의 x, y값과 범위의 size 그리고 배열 arr을 매개변수로 받아온다. check 함수를 통해 모든 수가 같은 값인지 확인한다. 만약 모두 같은값이라면 answer 배열에서 해당하는 index 값을 증가시킨다. 그리고 4등분으로 구분된 영역에 dp를 재귀함수로 호출한다.  

private static void dq(int startX, int startY, int size, int[][] arr) {
		if(check(startX, startY, size, arr)) {
			answer[arr[startX][startY]]++;
			return;
		}
		dq(startX, startY, size / 2, arr);
		dq(startX + size / 2, startY, size / 2, arr);
		dq(startX, startY + size / 2, size / 2, arr);
		dq(startX + size / 2, startY + size / 2, size / 2, arr);
	}

 

Solution

class Solution {
    
	static int[] answer = new int[2];
    
    public int[] solution(int[][] arr) {
        int totalSize = arr.length;
        dq(0,0,totalSize,arr);
        
        return answer;
    }
    
    	private static void dq(int startX, int startY, int size, int[][] arr) {
		if(check(startX, startY, size, arr)) {
			answer[arr[startX][startY]]++;
			return;
		}
		dq(startX, startY, size / 2, arr);
		dq(startX + size / 2, startY, size / 2, arr);
		dq(startX, startY + size / 2, size / 2, arr);
		dq(startX + size / 2, startY + size / 2, size / 2, arr);
	}

	private static boolean check(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;
	}
}

 

마치며

문제를 보자마자 분할정복이라는 걸 알았지만, 시뮬레이션처럼 구현하려다 보니 코드가 복잡해지고 산으로 간다는 느낌을 받았다. 다시 코드를 싹 밀어버리고... 3단계 규칙을 생각하여 문제를 풀었더니 아주 손쉽게 문제를 풀 수 있었다. 이 문제를 풀어보고 과거에 백준에서 풀었던 쿼드트리 문제가 생각나서 풀었던 코드를 확인했는데 출력포맷만 다를 뿐 로직은 거의 98퍼센트 일치한다는 걸 발견했다. 모든 알고리즘은 기본에 충실할 것,,, 그리고 복습을 철저히할 것을 새삼 느꼈다.

 

문제 바로가기

코딩테스트 연습 - 쿼드압축 후 개수 세기