835.Image Overlap

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

Explanation:

주어진 img1을 상, 하, 좌, 우로 움직여서 img2를 만들 때 가장 많이 겹칠 수 있는 수를 반환하는 문제이다.

Algorithm:

brute force

주어진 이미지의 크기를 모두 돌면서 img1과 img2에 존재하는 1을 각 배열에 저장한다. 어차피 문제에서 요구하는 것은 img1을 이동시켜서 img2에 겹치는 칸 수만 반환하면 되기 때문에 img1에서 움직여서 만들어진 img2라면 이동한 후의 좌표 - 이동하기 전의 좌표를 구하면 같은 값이 나오는 게 있을 것이다.

위와 같이, 겹치는 값을 hash table에 저장하고 매번 max값을 ans에 저장해주었다.

class Solution:
    def largestOverlap(self, A, B):
        """
        :type A: List[List[int]]
        :type B: List[List[int]]
        :rtype: int
        """
        d = collections.defaultdict(int)
        a = []
        b = []
        for i in range(len(A)):
            for j in range(len(A[0])):
                if(A[i][j] == 1):
                    a.append((i,j))
                if(B[i][j] == 1):
                    b.append((i,j))
        ans = 0
        for t1 in a:
            for t2 in b:
                t3 = (t2[0]-t1[0],t2[1]-t1[1])
                d[t3] += 1
                ans = max(ans, d[t3])
        return ans

Time Complexity:

n이 최대 30이고 2차원 배열 2개를 완전탐색하므로 30^4 = 810000 = O(N^4)정도로 보인다.