[프로그래머스 level_2 / 월간 코드 챌린지 시즌 1] 쿼드압축 후 개수 세기 for JAVA

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 x 4 도형일 경우, 해당 배열에 포함된 숫자가 모두 동일한지 체크해준다.

만약 아니라면, 네 부분으로 나눠준다. 맞다면 그 부분은 더 이상 탐색하지 않는다. 아래는 플로우를 작성한 것이다.

 

1. arr의 크기가 1이라면 해당 arr의 요소가 0인지, 1인지 세어준다.

2. arr의 크기가 1이 아니라면, 해당 arr의 요소가 같은 요소인지 세어준다.

2-1 같은 경우, 해당 부분에 해당하는 요소 (0 or 1)의 카운트를 증가시켜준다.

2-2 같지 않은 경우, 네 부분으로 나눠서 재귀 함수를 돌려준다.

 

* 문제를 풀 때 네 부분으로 인덱스 관리를 해줘야 하는데 아이디어는 다음과 같다.

-> 처음에는 0, 0에서 시작해서 len(arr의 길이) 만큼 탐색해준다.  0, 0에 해당하는 변수를 a, b라 하자.

만약 모든 요소가 같지 않아 네 부분으로 나뉘어야 한다면, 사각형은

1	2
3	4

이런 식으로 나뉠 것이다.

1 : a, b

2 : a, (b + len/2)

3 : (a + len/2) , b

4 : (a + len/2),  (b + len/2)

으로 시작 인덱스를 구할 수 있다.

 

 

예를 들어, 예제와 같이 len = 4일 때, arr의 요소가 같은 수가 아니라면, (a = 0,  b = 0)

0, 0	0, 1	0, 2	0, 3
1, 0	1, 1	1, 2	1, 3
2, 0	2, 1	2, 2	2, 3
3, 0	3, 1	3, 2	3, 3

(len = 4인 2차원 배열에서의 인덱스)

 

1 구역(보라색) : 0, 0     (a, b)

2 구역(파란색) : 0, 2     (a, (b + len/2))

3 구역(빨간색) : 2, 0     ((a + len/2) , b)

4 구역(밤색   ) : 2, 2     ((a + len/2),  (b + len/2))

 

위와 같이 판단해주면 된다. 더 자세한 내용은 코드를 보며 이해할 수 있을 수 있다.

 

 

[코드]

    int zero;
    int one;
 
    public int[] solution(int[][] arr) {
        zero = 0; // 리턴할 값 초기화
        one = 0;
        int arrLen = arr.length;
 
        recursive(arr, 0, 0, arrLen);
 
        return new int[] { zero, one };
    }
 
    public void recursive(int[][] arr, int a, int b, int len) {
        if(len == 1) {                                                        //종료 조건
            if(arr[a][b] == 0) {
                zero++;
            }else {
                one++;
            }
            return;
        }
        
        int value = arr[a][b];
        boolean flag = true;
        for (int i = a; i < a + len; i++) {
            if (flag) {
                for (int j = b; j < b + len; j++) {
                    if (value != arr[i][j]) {
                        flag = false;
                        break;
                    }
                }
            } else {
                break;
            }
        }
 
        if (flag) {                     // 같은 수 일 때
            if (value == 1) {
                one++;
            } else {
                zero++;
            }
        } else {
            len = len/2;
            
            recursive(arr, a, b, len);
            recursive(arr, a + len, b, len);
            recursive(arr, a, b + len, len);
            recursive(arr, a + len, b + len, len);
        }
 
    }
 

프로그래머스 테스트 케이스 통과

 

 

느낀 점: 처음에는 조금 고민이 필요했던 문제, 재귀 함수로 구현해보자 생각하고 금방 구현할 수 있었다. 문제풀이 방식을 생각해 내는 것이 가장 중요한 것 같다.