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

 

 

나의 풀이

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

    while n > 0:
        for x in range(k):
            for y in range(k):
                nx, ny = n * x, n * y
                temp = arr[ny][nx]
                if temp == -1:
                    continue
                for i in range(nx, nx + n):
                    for j in range(ny, ny + n):
                        if temp != arr[j][i]:
                            break
                    else:
                        continue
                    break
                else:
                    for i in range(nx, nx + n):
                        for j in range(ny, ny + n):
                            arr[j][i] = -1
                    answer[temp] += 1
        n //= 2
        k *= 2

    return answer

 

 

재귀를 이용한 풀이

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

    def check(size, x, y):
        if size == 1:
            answer[arr[y][x]] += 1
            return
        else:
            first = arr[y][x]

            for dy in range(size):
                for dx in range(size):
                    if first != arr[y + dy][x + dx]:
                        check(size // 2, x, y)
                        check(size // 2, x + size // 2, y)
                        check(size // 2, x, y + size // 2)
                        check(size // 2, x + size // 2, y + size // 2)
                        return
            answer[first] += 1
    check(len(arr),0,0)


    return answer

 

 

 

 

numpy를 활용한 풀이

import numpy as np

def solution(arr):
    # 재귀함수 구현
    def fn(a):
        if np.all(a == 0): return np.array([1, 0])
        if np.all(a == 1): return np.array([0, 1])
        n = a.shape[0]//2
        return fn(a[:n, :n]) + fn(a[n:, :n]) + fn(a[:n, n:]) + fn(a[n:, n:])

    # 결과 리턴
    return fn(np.array(arr)).tolist()