leetcode medium : Magic Squares In Grid

띠리링구 2023. 1. 15. 01:43

https://leetcode.com/problems/magic-squares-in-grid/description/

Magic Squares In Grid - LeetCode

Magic Squares In Grid - A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum. Given a row x col grid of integers, how many 3 x 3 "magic square" subgrids are the

leetcode.com

풀기 전에

뭔가 쉬워보이는데.. 꿍꿍이가 있는 문제일까?

특별히 뭔가 최적화할건 없는거같다.

초보자라면 sum 구해서 비교하는건 쉬워도 1~9 distinct 조건이 좀 어려울수도 있긴한데

이건 set에다 넣어서 길이 9인지 확인하고 min 값이랑 max값이 각각 1,9인지만 보면 된다.

class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        if len(grid) < 3 or len(grid[0]) < 3: return 0

        answer = 0

        for i in range(len(grid) - 2):
            for j in range(len(grid[0]) - 2):
                minnum = 16
                maxnum = -1
                dset = set()
                for k in range(3):
                    for l in range(3):
                        dset.add(grid[i+k][j+l])
                        minnum = min(minnum, grid[i+k][j+l])
                        maxnum = max(maxnum, grid[i+k][j+l])
                if minnum != 1 or maxnum != 9 or len(dset) != 9:
                    continue
                r = [sum(grid[i+y][j+x] for x in range(3)) for y in range(3)]
                c = [sum(grid[i+y][j+x] for y in range(3)) for x in range(3)]
                d1 = sum(grid[i+x][j+x] for x in range(3))
                d2 = sum(grid[i+2-x][j+x] for x in range(3))

                if r[0] == r[1] == r[2] == c[0] == c[1] == c[2] == d1 == d2:
                    answer += 1

        return answer

복잡도는 row길이 * col 길이에 비례하는듯하다.