문제
접근
0과 1의 개수만 세면 되기 때문에,
일반 적인 쿼드압축에서 배열을 유지하는 것과 다르게 0, 1의 개수만을 이용해봤다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def solution(arr):
answer = []
n = len(arr)
answer = quardTree(arr, 0, 0, n)
return answer
def quardTree(arr, x, y, n):
ans = [0,0]
quard = [0,0]*4
if n == 1:
ans[arr[y][x]]+=1
return ans
quard[0] = quardTree(arr, x, y, n//2)
quard[1] = quardTree(arr, x+n//2, y, n//2)
quard[2] = quardTree(arr, x, y+n//2, n//2)
quard[3] = quardTree(arr, x+n//2, y+n//2, n//2)
for i in range(4):
ans[0] += quard[i][0]
ans[1] += quard[i][1]
if ans[0]+ans[1] == 4 and ans[0] == 4:
return [1, ans[1]]
elif ans[0]+ans[1] == 4 and ans[1] == 4:
return [ans[0], 1]
else:
return ans