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

출처::월간 코드 챌린지, programmers.co.kr/learn/courses/30/lessons/68936?language=python3

분류:: 분할정복, 재귀

 

1. 문제 이해 및 해결과정

- 분할 정복의 대표적인 문제이다 - 네 부분으로 쪼개서 개수가 한개일때까지 반복해야한다 - 0으로만 이루어져 있거나, 1로만 이루어져 있으면 개수를 세고 - 0과 1이 섞여있으면 4개 영역으로 분할 된다  - 분할을 하기 위해서는 시작지점(h,w),크기,현재 배열이 필요하다

 

2. 풀이방법

  1. [ python ] 재귀 

onecnt,zerocnt=0,0
def quadTree(h,w,size,arr):
    global onecnt,zerocnt 
    one=True #1로만 이루어 졌을 때
    zero=True #0으로만 이루어 졌을 때 
    
    for i in range(h,h+size):
        for j in range(w,w+size):
            if arr[i][j]==1: #1이 하나라도 있으면
                zero=False #0으로만 이루어져 있지 않음
            if arr[i][j]==0: # 0이 하나라도 있으면
                one=False #1로만 이루어져 있지 않음 
        if zero==False and one==False: #0으로만,1로만 이루어져있지 않으면 더 돌릴 필요 없음 
            break
    if one==True: #1로만 이루어져있을 떄
        onecnt+=1 
    elif zero==True: #0으로만 이루어져 있을 때 
        zerocnt+=1
    else: #0과 1이 섞여있으면 분할 
        quadTree(h,w,size//2,arr) #4사분면
        quadTree(h,w+size//2,size//2,arr) #1사분면
        quadTree(h+size//2,w,size//2,arr) #3사분면
        quadTree(h+size//2,w+size//2,size//2,arr) #2사분면
        
def solution(arr):
    result=[]
    
    quadTree(0,0,len(arr),arr) #h,w,배열길이,answer
    result.append(zerocnt)
    result.append(onecnt)
    return result

 2. [ python ] numpy

import numpy as np
def solution(arr):
    def quadtree(x):
        #모두 0이라면
        if np.all(x==0): return np.array([1,0]) #0의 개수 추가
        #모두 1이라면
        if np.all(x==1): return np.array([0,1]) #1의 개수 추가
        n= x.shape[0]//2 #size 0.5배
        return quadtree(x[:n,:n])+quadtree(x[n:,:n])+quadtree(x[:n,n:])+quadtree(x[n:,n:])
       
    return quadtree(np.array(arr)).tolist() #array를 list형태로 변환

3. [ python ] 재귀

def solution(arr):
    result=[]
    def quadtree(h,w,size):
        cur=arr[h][w] #기준
        for i in range(h,h+size):
            for j in range(w,w+size):
                if arr[i][j]!=cur: #현재를 기준으로 다르면 분할 
                    quadtree(h,w,size//2)
                    quadtree(h,w+size//2,size//2)
                    quadtree(h+size//2,w,size//2)
                    quadtree(h+size//2,w+size//2,size//2)
                    return
        result.append(cur) 
    
    quadtree(0,0,len(arr))
    return [result.count(0),result.count(1)]

 

 

3. 오답원인

 

4. 알게된 점

리스트에서 개수세기 , 리스트 형태로 반환하기

return [result.count(0),result.count(1)]

result.count(0) #result리스트에서 0의 개수 세기