[プログラマ]四圧縮後のカウント

13572 ワード
アルゴリズム#アルゴリズム# パイ level2 プログラマ テキストリンク
使用するアルゴリズム/データ構造
これは問題の中で提出された条件を体現しなければならない問題である.
1回目の質問には次のような方法が使われました.
배열의 각 데이터를 2칸씩 for 문으로 돌면서 
2x2크기 확인 -> 맞을 경우 4x4크기 확인 -> ...
コード#コード#
def solution(arr):
    n = len(arr)
    compressed = [[False]*n for _ in range(n)]
    cnt = [0, 0]
    for i in range(0, n, 2):
        for j in range(0, n, 2):
            if compressed[i][j]:
                continue
            size = 2
            while check(i, j, n, size, arr):
                size *= 2
            if size > 2:
                compress(i, j, size//2, compressed)
                cnt[arr[i][j]] += 1
            else:
                for x in range(i, i + 2):
                    for y in range(j, j + 2):
                        cnt[arr[x][y]] += 1
    return cnt

def check(x, y, n, size, arr):
    if x%size != 0 or y%size != 0 or x+size > n or y+size > n:
        return False
    for i in range(x, x + size):
        for j in range(y, y + size):
            if arr[i][j] != arr[x][y]:
                return False
    return True

def compress(x, y, size, compressed):
    for i in range(x, x + size, 2):
        for j in range(y, y + size, 2):
            compressed[i][j] = True
コード改善方向
前述したように、すべてのデータを巡回してデータをチェックし、圧縮したデータを圧縮に保存し、圧縮していない場合は2 x 2格子を返して0/1をカウントする必要がある.
これにより、コードが複雑になり、管理する必要があるデータが多くなります.
これとは異なり、再帰文を使用して大きな面積を先に表示すると、アルゴリズムコードの変更が簡単になります.
(0, 0)에서 시작
nxn 확인 -> 실패 시 (n/2)x(n/2) 4개의 칸을 각각 확인 -> ...
改良されたコード
def solution(arr):
    cnt = [0, 0]
    def check(size, x, y):
        if size > 1:  
            for dx in range(size):
                for dy in range(size):
                    if arr[x+dx][y+dy] != arr[x][y]:
                        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
        cnt[arr[x][y]] += 1
    check(len(arr), 0, 0)
    return cnt
アルゴリズムは平均値を求めます
[スタック]有効なかっこ