835. Image Overlap

Image Overlap

Image Overlap - LeetCode

 

아래 문제와 동일한 문제이다.

2020/09/06 - [Problem Solving] - 자물쇠와 열쇠

- 문제 내용

두개의 이미지를 Overlap해서 가장 많이 Overlap 되는 1의 수를 구한다.

 

- 접근 방법

자물쇠와 열쇠 같이 "A이미지의 길이 -1 + B 이미지의 길이 + A이미지의 길이 -1" 로 하는 전체 보드를 생성하고 그 중간에 B의 이미지를 넣는다. 이를 full Board라고 부른다.

A의 이미지를 (0,0)에서 (B 길이 + A길이 -1)까지 순환을 시키며 full Board의 값과 cell 끼리 비교를 한다.

비교된 값이 1 & 1 일경우 count에 표시하고 A 이미지가 1회 Move 할때마다 max값과 count를 비교해서 큰 값을 유지하고, 이 값을 결과 값으로 내놓으면 된다.

var largestOverlap = function(A, B) {
    let fullSize = (A.length - 1) * 2 + B.length;
    let fullBoard = new Array(fullSize).fill(0).map(_=> new Array(fullSize).fill(0));
    let bStartPoint = A.length - 1;
    
    for(let row = 0; row < B.length; row ++){
        for(let col = 0; col < B.length; col++){
            fullBoard[bStartPoint+row][bStartPoint+col] = B[row][col];
        }
    }
    
    let max = 0;
    for(let row = 0; row < (A.length - 1) + B.length; row++){
        for(let col = 0; col < (A.length -1) + B.length; col++){
            
            let count = 0;
            for(let aRow = 0; aRow < A.length; aRow++){
                for(let aCol = 0; aCol < A.length; aCol++){
                    count += A[aRow][aCol] & fullBoard[aRow + row][aCol + col];
                }
            }
            
            max = Math.max(max, count);
        }
    }
    
    return max;
    
};

해당 문제는 다른 해결 방법이 몇가지 더 Leetcode에 솔루션으로 나왔는데 보면 Time complexity가 획기 적으로 줄어들지 않고, 반면에 Space Complexity가 높아지는 것으로 보인다.

- Time complexity : O(N^4)

시간 복잡도를 생각해 봐야 하는 문제 같다. 문제에서 A와 B의 length는 같은 것으로 생각하라고 했으니 이를 통합 시키겠다.

• fullboard : (A.length - 1) * 2 * B.length = O(3AL) = A.length 를 N이라고 부르겠다. = O(3N) = O(N)
• 외곽 순환 : O(2N -1 * 2N - 1) 
• 내곽 순환 : O(N * N)
• 외곽 순환 * 내곽 순환 = O(4N^2) * O(N^2) = O(N^4)

- Space Complexity : O(N)

full board를 하나 만드니까 N으로 처리 했다. 

계산을 편하게 하려고 Space를 만들긴 했는데, 필요 없이 처리 하는한 방법이 Solution에 있다. 해당 내용은 조금더 파악한뒤 올릴 예정이다.