[Programmers] 쿼드 압축 후 개수 세기

출처: 프로그래머스 - 쿼드 압축 후 개수 세기

언어: JAVA

 

 

1. 풀이 과정

문제를 요리보고 저리봐도 이건 재귀함수 문제다! (반복적으로 계속 압축하고 있기 때문)

☝  2차원 배열의 모든 수가 같은지 확인
✌  다를 시, 영역을 1/4로 나누기! 다를 시, 해당 숫자 카운트++

위의 과정을 배열의 길이 가 1이 될 때까지 반복하면 총 0과 1의 개수가 세어진다.

 

2차원 배열의 모든 수가 같은지 확인할 땐,

기준값(비교하려는 영역의 첫번째 값. 즉 첫번째 재귀 값에서는 arr[0][0])과 다른 값 존재 시

바로 영역 나누기(✌번째 과정)으로 넘어간다.

그러나 다른 값이 없는 경우 해당 숫자의 카운트를 증가시키고 재귀를 끝낸다.

 

그리고 영역을 나눌 땐 4개의 영역으로 나누기 때문에 4개의 재귀함수를 호출했다.

이 때, 재귀함수의 파라미터 값으로 (배열, 현재 배열 길이의 1/2, 기준값의 x좌표, 기준값의 y좌표) 를 넘겨주는데,

기준값의 x좌표와 y좌표는 현재 기준값의 좌표를 기준으로 나누는 영역에 맞게 배열 길이의 1/2값을 더해주었다.그러면 다음 재귀때, 넘겨받은 파라미터의 기준값 좌표로 값을 비교 할 수 있다.

 

말로 하니깐 너무 복잡하니,, (말못하는 이과생) 예시로 설명하겠다.

 

입출력 예#2

이 재귀함수에서 중요한 파라미터 값인 기준값 x좌표와 y좌표에 집중해서 보자!

 

** 첫 번째 재귀 **

기준값: arr[0][0]

비교결과: 다름❌

다음 기준값 (x, y)

: (0, 0), (0, 4), (4, 0), (4, 4)

 

** (0, 0)을 기준으로 두 번째 재귀 **

기준값: arr[0][0]

비교결과: 다름❌

다음 기준값 (x, y)

: (0, 0), (0, 2), (2, 0), (2, 2)

 

** (2, 0)을 기준으로 두 번째 재귀 **

기준값: arr[2][0]

비교결과: 다름❌

다음 기준값 (x, y)

: (2, 0), (2, 1), (3, 0), (3, 1)

 

.

.

.

 

위 값들을 보면

기준값(x, y)를 기준으로 다음 기준값은

(x, y), (x, y + length/2), (x + length/2 , y), (x + length, y + length) 라는 것을 알 수 있다.

 

따라서 (x, y), (x, y + length/2), (x + length/2 , y), (x + length, y + length) 값으로 재귀함수를 계속 호출하다보면,

0과 1의 총 개수를 알 수 있다.

 

2. 주요 코드

    private static void compression(int[][] arr, int length, int start, int end) {
    	boolean bolChk = true;
    	int flagNum = arr[start][end];
    	
    	for (int i = start; i < start + length; i++) {
			for (int j = end; j < end + length; j++) {
				if (arr[i][j] != flagNum) {
					bolChk = false;
					break;
				}
			}
		}
    	
    	if (bolChk) {
			if (flagNum == 1) {
				oneCnt++;
			} else if (flagNum == 0) {
				zeroCnt++;
			}
		} else {
			compression(arr, length/2, start, end);
			compression(arr, length/2, start, end + length/2);
			compression(arr, length/2, start + length/2, end);
			compression(arr, length/2, start + length/2, end + length/2);
		}
	}

* 전체 코드