[Python] 프로그래머스 Lv.02 - 쿼드압축 후 개수 세기

programmers.co.kr/learn/courses/30/lessons/68936

코딩테스트 연습 - 쿼드압축 후 개수 세기

[ 알고리즘 ]

구현

 

[문제 접근]

아이디어가 필요한 문제이다. 2*2 형태로 [0의 개수,1의 개수를 구해준 후] 계속해서 반씩 더하며 줄여나가는 형태이다.

이때 [4,0] 과 같이 ( 0의 개수가 4개, 1의 개수가 0개) 같은 것은 0으로 압축할 수 있기 때문에 [1,0] 으로 바꿔주면된다

 

예를들어,

arr=[[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] 일때

[1,3],[4,0]... 이런식으로 압축

 

[코드]

import copy
def solution(arr):
    answer = []
    n=len(arr)
    List=[[] for _ in range(n//2)]
    
    # [0의 개수,1의 개수] 형태로 만들기
    for i in range(1,n,2):
        for j in range(1,n,2):
            cnt=[0,0]
            
            if arr[i][j]==0:cnt[0]+=1
            else:cnt[1]+=1
            
            if arr[i-1][j-1]==0:cnt[0]+=1
            else:cnt[1]+=1
            
            if arr[i-1][j]==0:cnt[0]+=1
            else:cnt[1]+=1
            
            if arr[i][j-1]==0:cnt[0]+=1
            else:cnt[1]+=1
                
            if cnt[0]==0:
                cnt[1]=1
            elif cnt[1]==0:
                cnt[0]=1
            
            List[i//2].append(cnt)

    while True:
        n=len(List)
        result=[[] for _ in range(n//2)]
        
        for i in range(1,n,2):
            for j in range(1,n,2):
                a=List[i][j][0]+List[i-1][j-1][0]+List[i-1][j][0]+List[i][j-1][0]
                b=List[i][j][1]+List[i-1][j-1][1]+List[i-1][j][1]+List[i][j-1][1]
                
                if a==0:
                    b=1
                if b==0:
                    a=1
                    
                result[i//2].append([a,b])

        List=copy.deepcopy(result)
        
        if len(result)==1:
            return result[0][0]
        
    return answer