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

링크 programmers.co.kr/learn/courses/30/lessons/68936?language=python3#

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

처음에는 리스트를 4개로 나누어줬는데, 계속 시간초과가 되서 리스트를 직접 만들지 않고 포인터처럼 r, c가 왔다갔다 하게 구현했다. 그리고 처음에 바로 나누어주고 시작하는거 때문에 10번 테스트케이스(처음 입력받은 배열 arr 전체가 쿼드 압축 가능한 경우)를 처리해주려고 코드가 복잡하게 짜여졌는데, 이왕 새로짜는 김에 처리 순서도 바꿨다.

 

시간 초과

def solution(arr):
    
    answer = [0, 0]

    def quad_tree(arr):
        tot = sum(arr, [])
        n = len(arr)
        mid = n//2
        if sum(tot) == 0:
            answer[0] += 1
        elif sum(tot) == len(tot):
            answer[1] += 1
        else:
            current = {0: 0, 1: 0, 2: 0, 3: 0}
            divide = [[],[],[],[]]
            for i in range(n):
                row = [[],[],[],[]]
                for j in range(n):
                    val = arr[i][j]
                    if i in range(0, mid) and j in range(0, mid):
                        current[0] += val
                        row[0].append(val)
                    elif i in range(0, mid) and j in range(mid, n):
                        current[1] += val
                        row[1].append(val)
                    elif i in range(mid, n) and j in range(0, mid):
                        current[2] += val
                        row[2].append(val)
                    else:
                        current[3] += val
                        row[3].append(val)
                for i in range(4):
                    if row[i]:
                        divide[i].append(row[i])
            for i in range(4):
                if current[i] == (mid)**2:
                    answer[1] += 1
                elif current[i] == 0:
                    answer[0] += 1
                else:
                    quad_tree(divide[i])

    quad_tree(arr)
    
    return answer

print(solution([[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]]))

 

해결 

def solution(arr):
    answer = [0, 0]
    n = len(arr)

    def divide(r, c, n):
        num = arr[r][c]
        for i in range(r, r+n):
            for j in range(c, c+n):
                if num != arr[i][j]:
                    divide(r, c, n//2)
                    divide(r+n//2, c, n//2)
                    divide(r, c+n//2, n//2)
                    divide(r+n//2, c+n//2, n//2)
                    return
        answer[num] += 1
    
    divide(0, 0, n)
    return answer

print(solution([[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]]))