[Programmers] 쿼드압축 후 개수 세기 바로가기
0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.
arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.
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
[4,9]
를 return 해야 합니다.입출력 예 #2
[10,15]
를 return 해야 합니다.return
의 값을 주는 이유는 현재 배열은 쿼드 압축이 불가능해서 4분할을 진행한 후 코드가 종료되어야 하는데 만약 return
이 존재하지 않는다면 그대로 코드가 진행하여 마치 현재 배열이 쿼드 압축이 가능한 것처럼 answer
의 target
에 대한 값이 1 증가하기 때문에 이를 막기 위해 return
문을 작성한다.def solution(arr):
answer = [0, 0]
def compress(x,y,n):
target = arr[y][x]
for i in range(y,y+n):
for j in range(x,x+n):
if target != arr[i][j]:
n //= 2
compress(x,y,n)
compress(x+n,y,n)
compress(x,y+n,n)
compress(x+n,y+n,n)
return
answer[target] += 1
compress(0,0,len(arr))
return answer