835. Image Overlap

2026-04-09
leetcode
Leetcode 835번 풀이

문제

Image Overlap

풀이

아이디어

img1을 (dy, dx)만큼 이동시켰을 때 img2와 1이 겹치는 개수를 세는 문제다.

이동 가능한 offset 범위는 dy, dx ∈ [-(n-1), n-1]로, 총 (2n-1)²가지다. 사실 다른 방법이 생각이 안나서 긴가민가하면서 4중 for문으로 구현했는데, 풀고 나서 리뷰를 받아보니 n=30이면 3481가지로 완전 탐색이 가능하다.

실제로 행렬을 shift할 필요는 없다. (dy, dx)가 주어졌을 때, img1[i+dy][j+dx]와 img2[i][j]를 비교하되 i+dy, j+dx가 유효한 범위(0 ~ n-1) 안에 있는 경우만 확인하면 된다.

0과 1값을 다루는 이점을 누리기 위해서 (ㅎㅎ) 비트 연산자 &를 사용하여 겹치는 부분을 계산해줬다.

코드

function largestOverlap(img1: number[][], img2: number[][]): number {
  const n = img1.length;
  let max = 0;

  // 모든 이동 케이스 구해주기
  for (let dy = -n + 1; dy <= n - 1; dy++) {
    for (let dx = -n + 1; dx <= n - 1; dx++) {
      // dx, dy만큼 shift한 이미지를 구하고 있습니다.
      let overlap = 0;
      for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
          if (i + dy < 0 || i + dy >= n || j + dx < 0 || j + dx >= n) continue;
          overlap += img1[i + dy][j + dx] & img2[i][j];
        }
      }

      max = Math.max(overlap, max);
    }
  }

  return max;
}

시간 / 공간 복잡도

  • 시간 복잡도: O(N^4) - 이동 offset (dy, dx) 조합 O(N^2) × 각 offset마다 행렬 전체 비교 O(N^2)
  • 공간 복잡도: O(1)