프로그래머스 쿼드압축 후 개수 세기

🙂 문제 - 쿼드압축 후 개수 세기

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

🖐풀이 방법

• 프로그래머스에서 LEVEL 2로 되어있다.

1. 1024가 제한사항임으로 완전탐색을 진행 해도 될 것이라 생각했다.
2. 전체 크기 부터 보면서 2로 나누어가며 보면 분할 한 것 처럼 볼 수 있다.
3. 문제에 나온 법칙 + 완전탐색을 2로 나누어 가며 풀기

• ps. 재귀함수로 풀어야 겠다는 생각을 했는데 그냥 푼거 같다.. 다음에는 재귀함수 코드도 작성하여 같이 올리면 좋을 것 같다.

📃 CODE

   def slice(sx,sy,x,y,vst,ans):
   	flag = False
       
   	if vst[sx][sy] ==-1:
       	return vst,ans
           
   	be = vst[sx][sy]
       
   	for i in range(sx,x):
		if flag:
      		     	break
       		for j in range(sy,y):
           		if be != vst[i][j]:
               		flag = True
               		break
           		be= vst[i][j]
   
   	if flag==False:
       		ans[vst[sx][sy]]+=1
       		for i in range(sx,x):
           		for j in range(sy,y):
               		vst[i][j] = -1
   	return vst,ans
def solution(arr):
   answer = [0,0]
   check = len(arr)
   
   while(1):
       
 	 for i in range(0,len(arr),check):
		for j in range(0,len(arr),check):
			arr,answer = slice(i,j,i+check,j+check,arr,answer)
              
       	 check = check//2
       	 if check ==1:
           	break
               
   for i in range(len(arr)):
       for j in range(len(arr)):
           if arr[i][j] == -1:
               continue
           answer[arr[i][j]]+=1
      
   return answer

• 풀이가 많이 더럽습니다... clean code 꼭하기..