The Grid Search

https://www.hackerrank.com/challenges/the-grid-search/problem

 

빠른 탐색을 위해 2차원 부분합을 사용했는데... 오히려 문제가 있었다. 예를 들면 다음이 같은 결과로 나와서 그랬다.

sum([1,0,0]) == sum([0,0,1])

결국 부분합은 빠른 인덱스 탐색을 위해서만 사용하고, 부분합이 서로 같은 곳을 발견하면 거기서는 문자열 매칭을 통해 일치 여부를 조사했다. 선배들의 사례를 보니 루프만 돌려도 충분한 것 같다... 

def gridSearch(G, P):
    grid_sum = [0] * len(G)
    for i in range(len(grid_sum)):
        grid_sum[i] = [0] * len(G[0])

    for y, row in enumerate(G):
        s = 0
        for x, v in enumerate(row):
            s += int(v)

            if y:
                grid_sum[y][x] = grid_sum[y - 1][x] + s
            else:
                grid_sum[y][x] = s

    pat_sum = 0
    for i, pat in enumerate(P):
        pat_sum += sum(int(v) for v in pat)

    height = len(P)
    width = len(P[0])

    for sy in range(height - 1, len(G)):
        for sx in range(width - 1, len(G[y])):
            subsum = grid_sum[sy][sx]
            py = sy - height
            px = sx - width

            if py >= 0 or px >= 0:
                if py >= 0:
                    subsum -= grid_sum[py][sx]
                if px >= 0:
                    subsum -= grid_sum[sy][px]
                if py >= 0 and px >= 0:
                    subsum += grid_sum[py][px]

            if subsum != pat_sum:
                continue

            for i, y in enumerate(range(sy - height + 1, sy)):
                t0 = G[y][sx - width + 1:sx + 1]
                t1 = P[i]

                if t0 != t1:
                    break
            else:
                return 'YES'

    return 'NO'