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

https://programmers.co.kr/learn/courses/30/lessons/68936

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

---

문제

문제 설명

0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.

• 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
• 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
• 그렇지 않다면, 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]

---

입출력 예 설명

입출력 예 #1

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

• 

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

입출력 예 #2

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

• 

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

---

풀이

풀이 과정

데이터를 추출할 배열, 시작점의 x 좌표, 시작점의 y 좌표, 한 변의 길이를 파라미터로 받는 함수를 생성한다

정수 배열에서 시작점의 값과 압축 가능 여부를 변수로 선언해두고 효율성을 위해 더이상 쪼갤 수 없는 경우를 먼저 확인한다.
만약 한 변의 길이가 1이라면 이미 가장 작은 크기의 영역이기 때문에 시작점의 값이 0이라면 0의 개수를 증가시키고 1이라면 1의 개수를 증가시키고 탐색을 종료한다

private static void comp(int[][] arr, int x, int y, int length) {
        int s = arr[x][y]; //시작점의 값
        boolean canComp = true; //압축 가능 여부
		
        if(length == 1) { //더이상 쪼갤 수 없을 때
            if(s == 0) answer[0]++;
            else answer[1]++;
			
            return;
        }
}

 

다음으로 압축이 가능한 경우와 불가능한 경우를 나누어 탐색하기위해 압축 가능여부를 확인한다

배열 안에서 시작점의 값과 다른 값이 존재한다면 그 영역은 압축이 불가능한 영역이 된다

check:
for(int i = x; i < x + length; i++) {
    for(int j = y; j < y + length; j++){
        if(arr[i][j] != s) {
            canComp = false;
            break check;
        }
    }
}

 

압축이 가능한 경우라면 더이상 쪼갤 수 없는 경우와 마찬가지로 시작점의 값으로 정답을 증가시킨다

압축이 불가능한 경우라면 해당 영역을 다시 4개의 영역으로 나누어 탐색을 반복한다

if(canComp) { //압축이 가능 할 경우
    if(s == 0) answer[0]++;
    else answer[1]++;
}
else { //압축이 불가능 할 경우
    for(int i = x; i < x + length; i += length / 2) {
        for(int j = y; j < y + length; j += length / 2) {
            comp(arr, i, j, length / 2);
        }
    }
}

 

최종 코드

class Solution {

    static int[] answer = new int[2];
    
    public int[] solution(int[][] arr) {
        
        comp(arr, 0, 0, arr.length);
        
        return answer;
    }
    
    // 데이터를 추출할 배열, 시작점 x 좌표, 시작점 y 좌표, 한 변의 길이
    private static void comp(int[][] arr, int x, int y, int length) {
        int s = arr[x][y]; //시작점의 값
        boolean canComp = true; //압축 가능 여부
		
        if(length == 1) { //더이상 쪼갤 수 없을 때
            if(s == 0) answer[0]++;
            else answer[1]++;

            return;
        }

        check:
        for(int i = x; i < x + length; i++) {
            for(int j = y; j < y + length; j++){
                if(arr[i][j] != s) {
                    canComp = false;
                    break check;
                }
            }
        }

        if(canComp) { //압축이 가능 할 경우
            if(s == 0) answer[0]++;
            else answer[1]++;
        }
        else { //압축이 불가능 할 경우
            for(int i = x; i < x + length; i += length / 2) {
                for(int j = y; j < y + length; j += length / 2) {
                    comp(arr, i, j, length / 2);
                }
            }
        }
    }
}

---