Image Overlap - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com

아래 문제와 동일한 문제이다.
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;
};
javascript
해당 문제는 다른 해결 방법이 몇가지 더 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에 있다. 해당 내용은 조금더 파악한뒤 올릴 예정이다.
'Problem Solving' 카테고리의 다른 글
Shortest path in a Binary Maze (0) | 2020.09.08 |
---|---|
Word Pattern (0) | 2020.09.07 |
1579. Remove Max Number of Edges to Keep Graph Fully Traversable (0) | 2020.09.06 |
5509. Minimum Deletion Cost to Avoid Repeating Letters (0) | 2020.09.06 |
5508. Number of Ways Where Square of Number Is Equal to Product of Two Numbers (0) | 2020.09.06 |