Daily LeetCode Challenge - 835. Image Overlap

Problem From.
https://leetcode.com/problems/image-overlap/

오늘 문제는 Brutal Force 로 풀 수 있는 문제였다.

두개의 이미지가 주어지고, img1 을 한칸씩 옮겨서 img2 와 겹치는 부분중에서 1의 갯수가 제일 많은 경우를 반환하는 문제였다.

nXn 매트릭스 이기에 범위를 -n ~ n 으로 잡고 옮길수 있는 최대치까지 옮겨가면서 겹치는 1의 최대 갯수를 반환하였다.

class Solution {
    fun largestOverlap(img1: Array<IntArray>, img2: Array<IntArray>): Int {
        
        val n = img1.size
        var answer = 0
        for (x in -n..n) {
            for (y in -n..n) {
                var acc = 0
                for (i in 0 until n) {
                    for (j in 0 until n) {
                        val k = img2[i][j]
                        val t = getValue(i + x, j + y, img1)
                        if (k == 1 && t == 1) {
                           acc++
                        }
                    }
                }
                answer = Math.max(answer, acc)
            }
        }
        return answer
    }
    
    private fun getValue(i: Int, j: Int, a: Array<IntArray>): Int {
        if (i < 0 || j < 0 || i >= a.size || j >= a.size) return 0
        return a[i][j]
    }
}

시간복잡도는 O(n^4) 공간복잡도는 O(n^2) 가 나오게 된다.
개인적으로 Brutal Force 문제는 풀고 나서 재미가 크게 느껴지지는 않는것 같다.