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