문제
https://school.programmers.co.kr/learn/courses/30/lessons/64065
2^n x 2^n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축
입력
2차원 int 배열
[[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]]출력
arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return
풀이
제한조건
- arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다. 즉, arr의 행의 개수는 1, 2, 4, 8, ..., 1024 중 하나입니다.
- arr의 각 행의 길이는 arr의 행의 개수와 같습니다. 즉, arr은 정사각형 배열입니다.
- arr의 각 행에 있는 모든 값은 0 또는 1 입니다.
접근방법
대표적인 분할정복 문제이다.
우선 쿼드 트리를 이해하고 오자.
https://en.wikipedia.org/wiki/Quadtree
입력 예시를 통해 쉽게 살펴보자.
1. 전체를 4개의 영역으로 나눈다.
2. 나눈 영역이 모두 같은 값을 가지면, 하나의 값으로 압축을 한다.
(예시의 우측 상단 영역을 한 번 더 나눈다면 모두 0이므로, 해당 영역은 0000 -> 0으로 압축)그렇다면, 문제를 풀기 위해 흐름을 정리해보자.
1. 전체 영역을 4개의 영역으로 나눈다.
2. 나누어진 영역에 대해, 나눌 수 있다면 다시 4개의 영역으로 나눈다.
3. 더이상 나눌 수 없다면 해당 영역의 값을 반환.
4. 나누어진 4개의 영역이 모두 같은 값이면 압축.
5. 마지막으로 0과 1의 갯수 카운팅.전체의 영역을 4개로 어떻게 나눌 수 있을까.
각 영역의 좌측 상단의 좌표를 구해보자.
예시 입력의 경우, 전체 크기가 4이다.
(0,0), (0,2), (2,0), (2,2)이다.
즉 0을 기준으로 크기의 절반을 더해서 기준 좌표를 구할 수 있다.
이제 영역을 분할해서 압축된 코드를 구하고, 다시 분할된 코드를 합치는 과정을 통해 답을 구할 수 있다.
아래 문제와 유사하다.
이 문제를 제대로 이해했다면, 아래 문제도 쉽게 풀 수 있다.
https://www.acmicpc.net/problem/1992
https://www.acmicpc.net/problem/1074
코드
class Solution {
public int[] solution(int[][] arr) {
int size = arr.length;
String result = getCode(arr, 0, 0, size);
// 압축된 전체 코드를 구했다. 0의 갯수를 구해보자.
// 1의 갯수는 전체길이에서 0의 갯수를 뺀것이다.
int count = 0;
for(int i = 0 ; i < result.length(); ++i)
if(result.charAt(i) == '0')
count++;
int[] answer = new int[2];
answer[0] = count;
answer[1] = result.length() - count;
return answer;
}
public String getCode(int[][] arr, int baseX, int baseY, int size){
if(size == 1){
// 더이상 분해할 수 없다. 현재 코드를 리턴
return Integer.toString(arr[baseX][baseY]);
}
int newSize = size / 2;
String[] result = new String[4];
result[0] = getCode(arr, baseX, baseY, newSize); // 좌상단
result[1] = getCode(arr, baseX + newSize, baseY, newSize); // 우상단
result[2] = getCode(arr, baseX, baseY + newSize, newSize); // 좌하단
result[3] = getCode(arr, baseX + newSize, baseY + newSize, newSize); // 우하단
boolean flag = true;
String base = result[0];
for(int i = 0 ; i < 4; ++i){
if(!result[i].equals(base)){
flag = false;
break;
}
}
// 4개의 영역이 모두 같고, 길이가 1인 경우 압축이 가능한 경우다.
if(flag && base.length() == 1){
return base;
}else{ // 압축이 불가능할때는 압축 전 코드를 더해서 반환
return result[0] + result[1] + result[2] + result[3];
}
}
}