835. Image Overlap

[zeikar]

Problem Link

https://leetcode.com/problems/image-overlap/

Problem Summary

n x n 이진 행렬 img1을 상하좌우로만 평행이동해서 img2 위에 겹쳤을 때, 둘 다 1인 칸의 최대 개수를 구하는 문제.

Solution

n이 최대 30이라 평행이동을 전부 해봐도 (2n-1)^2 = 3481번이다. 그냥 다 돌려보면 된다.

처음에는 (3n-1) x (3n-1) 보드를 깔고 img1을 실제로 옮겨 그려서 셌는데 시간 초과가 났다.
이동할 때마다 보드 7921칸을 0으로 채우는데 실제로 겹치는 영역은 평균 100칸 정도라 거의 다 낭비다. 옮겨 그릴 필요 없이 img1[x+r][y+c]랑 img2[x][y]를 바로 비교하면 된다.

그래도 x, y를 0부터 n-1까지 다 돌면서 범위 밖을 continue로 거르니 절반밖에 안 줄었다. 처음부터 겹치는 범위만 돌면 된다.

img2[x]    를 읽으려면   x 가 0 이상 n 미만
img1[x+r]  를 읽으려면   x 가 -r 이상 n-r 미만
=> range(max(0, -r), min(n, n-r))

여기서 max(r, 0)으로 잘못 써서 한 번 틀렸다... 파이썬은 음수 인덱스를 에러 없이 뒤에서부터 읽어서 조용히 틀린다.

n=30 최악 입력에서 0.46s, 0.21s, 0.074s 순으로 줄었다. 시간복잡도는 O(n^4)

Source Code

class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        n = len(img1)
        res = 0

        for r in range(-n, n):
            for c in range(-n, n):
                cnt = 0
                for x in range(max(-r, 0), min(n-r, n)):
                    for y in range(max(-c, 0), min(n-c, n)):
                        cnt += 1 if img1[x+r][y+c] == img2[x][y] and img2[x][y] == 1 else 0

                res = max(res, cnt)

        return res