[LeetCode] 835.Image Overlap

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

Image Overlap - LeetCode

 

 

 

 

1. 문제 설명 

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

 

 

 

2. 접근 방식 

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

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

 

 

3. 주석 달기 (변수 설명, 각 줄마다 문장으로 설명, 함수 설명)

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

 

 

4. 분석

1. Time : n이 최대 30이고 2차원 배열 2개를 완전탐색하므로 30^4 = 810000 = O(N^4)정도로 보인다. 
2. Space :
3. 소요시간 : 40분 
4. 제출 횟수 (무작정 제출하기 않기)  : 3회
5. 어려웠던 부분과 해결한 방법 : 
6. 실수가 줄어들었는가 ?