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

 

https://school.programmers.co.kr/learn/courses/30/lessons/68936

 

프로그래머스

def quad(arr,x,y,size,dic):
    isCombine=True # 합쳐졌는지
    begin=arr[x][y] # 기준좌표
    for i in range(x,x+size):
        for j in range(y,y+size):
            if arr[i][j]!=begin: # 기준좌표와 다른게있으면 합쳐지지않음
                isCombine=False
        if isCombine==False:
            break
    if isCombine: # 합쳐졌으면 그 숫자를 더해줌
        dic[str(begin)]+=1
        return;
    
    new_size=int(size*0.5) # 절반으로 범위를 줄임
    quad(arr,x,y,new_size,dic) # 2사분면
    quad(arr,x,y+new_size,new_size,dic) # 1사분면
    quad(arr,x+new_size,y,new_size,dic) # 3사분면
    quad(arr,x+new_size,y+new_size,new_size,dic) # 4사분면

def solution(arr):
    dic={"0":0,"1":0}
    size=len(arr[0])
    quad(arr,0,0,size,dic)
    return [dic["0"],dic["1"]]

쿼드압축은 4개로 나눈 뒤 영역이 같은 숫자들로 이루어져있으면 하나로 압축하고, 같은숫자들이 아니면 다시 4개로 나눈다.