URL 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을 4등분하여, 해당 arr의 원소가 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
29
30
31
32
33
34
35
36
37
38
39
import numpy as np
answer = {'0': 0, '1' : 0}
def solution(arr):
if len(set(np.ravel(np.array(arr)))) == 1:
answer[str(list(set(np.ravel(arr)))[0])] += 1
else :
num = int(len(arr) / 2)
arr1 = np.array(arr)[:num, :num]
if len(set(np.ravel(arr1))) == 1:
answer[str(list(set(np.ravel(arr1)))[0])] += 1
else:
solution(arr1)
arr2 = np.array(arr)[:num, num:]
if len(set(np.ravel(arr2))) == 1:
answer[str(list(set(np.ravel(arr2)))[0])] += 1
else:
solution(arr2)
arr3 = np.array(arr)[num:, :num]
if len(set(np.ravel(arr3))) == 1:
answer[str(list(set(np.ravel(arr3)))[0])] += 1
else:
solution(arr3)
arr4 = np.array(arr)[num:, num:]
if len(set(np.ravel(arr4))) == 1:
answer[str(list(set(np.ravel(arr4)))[0])] += 1
else:
solution(arr4)
return list(answer.values())
1
2
3
answer = {'0': 0, '1' : 0}
arr = [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]]
solution(arr)
1
[4, 9]
1
2
3
answer = {'0': 0, '1' : 0}
arr = [[0,0],[0,0]]
solution(arr)
1
[1, 0]
1