쿼드압축

문제 설명

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 입니다.

입출력 예

입력1 :

출력1 :  
```[4,9]```

입력2 :  

[[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]]

출력2 :  
```[10,15]```
 </div>
</details>
<details>
<summary>작성코드</summary>
<div markdown="1">

```python

def solution(arr):
    return quadcomp(arr)
def quadcomp(arr):
    answer=[]
    if len(arr)==1:
        if arr[0][0]==1:
            return [0,1]
        return [1,0]
    left,right=[],[]
    for row in arr[:len(arr)//2]:
        left.append(row[:len(arr)//2])
        right.append(row[len(arr)//2:])
    answer.append(quadcomp(left))
    answer.append(quadcomp(right))
    left,right=[],[]
    for row in arr[len(arr)//2:]:
        left.append(row[:len(arr)//2])
        right.append(row[len(arr)//2:])
    answer.append(quadcomp(left))
    answer.append(quadcomp(right))
    answer=list(zip(*answer))
    if all(answer[0]) and answer[1].count(0)==len(answer[1]):
        return [1,0]
    elif all(answer[1]) and answer[0].count(0)==len(answer[0]):
        return [0,1]
    return [sum(answer[0]),sum(answer[1])]

개인적인 풀이

먼저, 분할정복과 재귀를 사용하여 이 문제를 풀었다.
우선적으로, 무조건 한 네모를 4등분 하고, 각 4등분된 곳에서 0과 1의 개수를 알아내면 되는것이다.
만일 4등분 된 조각이 모두 같은 숫자일 경우, 그 숫자 1개가 있다고 생각하며 return한다.
이런 간단한 방법으로 생각을 했는데, 실행 제한시간이 10초인데 10초에 육박하게 아슬아슬하게 통과하였다.
이게 왜 그런가 함께 스터디 하는 인원의 코드와 비교를 해보니, 만약 모든 숫자들이 0 또는 1로 이루어져 있을 경우에 가장 작은네모(1칸네모)부터 전체 네모까지 수많은 재귀를 해야하는 반면,
재귀가 시작되었을때 새로이 그 네모가 한 숫자로 이루어져있는지를 검사한 경우에는 더 좋은 성능을 내었다.
물론 테스트케이스를 모두 아는것이 아니기 때문에 확실히는 모르지만, 사각형의 크기가 작거나 통일된 숫자가 적을 경우에는 내가 쓴 방법이 더 효율적일 것이고,
사각형의 크기가 크거나 통일된 숫자가 많을 경우에는 사전에 통일된 사각형을 빠르게 처리하는 쪽이 더 성능이 좋을것이다.