[LeetCode] 840. Magic Squares In Grid

문제

row x col 크기의 정수 grid 가 주어질 때, 그 안에 있는 3x3 매직 스퀘어 부분 grid 의 개수를 구한다.

매직 스퀘어의 조건은 다음과 같다.

• 1부터 9까지 서로 다른 숫자로 채워져 있다.
• 각 행, 각 열, 두 대각선의 합이 모두 같다.

제약 조건

• 1 <= row, col <= 10
• 0 <= grid[i][j] <= 15

처음에 헷갈렸던 부분

"숫자가 고유해야 한다면서 [[5,5,5],[5,5,5],[5,5,5]] 같은 입력이 왜 들어오지?"

고유해야 한다는 조건은 입력 grid 에 걸린 게 아니라 매직 스퀘어가 되기 위한 조건이다. 입력 제약은 0 <= grid[i][j] <= 15 뿐이라서 grid 에는 같은 숫자가 여러 번 나와도 되고, 0 이나 10~15 도 들어올 수 있다.

처음에는 합만 비교해서 틀렸다. 5로만 채운 판은 행·열·대각선 합이 전부 15라서 통과해 버린다.

놓치기 쉬운 함정 3가지

1. 1~9 가 한 번씩 쓰였는지 확인해야 한다

합이 같은지만 보면 5 5 5 / 5 5 5 / 5 5 5 같은 판을 걸러내지 못한다.

2. "서로 다른 9개"만으로는 부족하고 범위도 확인해야 한다

중복 검사만 추가해도 아직 틀린다. 1~9 매직 스퀘어의 모든 칸에 1을 더하면

5 10 3
4  6 8
9  2 7

9개가 모두 다르고 행·열·대각선 합도 모두 18이다. 하지만 10이 들어 있으니 정답이 아니다. 그래서 모든 값이 1 이상 9 이하인지도 확인해야 한다.

3. 행 합, 열 합, 대각선 합을 서로 비교해야 한다

행끼리, 열끼리, 대각선끼리만 같은지 보면 "행 합은 모두 6, 열 합은 모두 12" 같은 경우를 놓친다. 마지막에 세 값이 서로 같은지 한 번 더 비교한다.

풀이

1. 3x3 부분 grid 의 왼쪽 위 좌표 (i, j) 를 grid 안에서 가능한 범위로 모두 돈다.
2. 각 부분 grid 에서
   • 9개 값이 모두 1~9 범위이고 서로 다른지 확인한다.
   • 각 행의 합이 같고, 각 열의 합이 같고, 두 대각선의 합이 같은지 확인한다.
   • 행 합, 열 합, 대각선 합이 서로 같은지 확인한다.
3. 모두 통과하면 개수를 센다.

코드

function numMagicSquaresInside(grid: number[][]): number {
    const row = grid.length;
    const col = grid[0].length;
    let magicSquares = 0;

    const isMagicSquare = (y: number, x: number) => {
        const distinct = new Set<number>();
        for (let i = y; i < y + 3; i++) {
            for (let j = x; j < x + 3; j++) {
                const v = grid[i][j];
                if (v < 1 || 9 < v) return false;
                distinct.add(v);
            }
        }
        if (distinct.size !== 9) return false;

        const rowSum = grid[y][x] + grid[y][x + 1] + grid[y][x + 2];
        const colSum = grid[y][x] + grid[y + 1][x] + grid[y + 2][x];
        const diagonalSum = grid[y][x] + grid[y + 1][x + 1] + grid[y + 2][x + 2];
        for (let i = 0; i < 3; i++) {
            const curRowSum = grid[y + i][x] + grid[y + i][x + 1] + grid[y + i][x + 2];
            if (curRowSum !== rowSum) return false;
            const curColSum = grid[y][x + i] + grid[y + 1][x + i] + grid[y + 2][x + i];
            if (curColSum !== colSum) return false;
        }
        const curDiagonalSum = grid[y + 2][x] + grid[y + 1][x + 1] + grid[y][x + 2];
        if (diagonalSum !== curDiagonalSum) return false;
        if (rowSum !== colSum || colSum !== diagonalSum) return false;

        return true;
    };

    for (let i = 0; i < row; i++) {
        if (i + 2 >= row) break;
        for (let j = 0; j < col; j++) {
            if (j + 2 >= col) break;
            if (isMagicSquare(i, j)) magicSquares++;
        }
    }

    return magicSquares;
}

복잡도

• 시간: O(row × col). 부분 grid 마다 하는 검사는 9칸으로 고정이다.
• 공간: O(1). Set 에는 최대 9개만 들어간다.

더 생각해 볼 점

1~9 를 한 번씩 쓰면 전체 합이 45이므로 한 줄의 합은 항상 15다. 게다가 매직 스퀘어의 중앙은 항상 5다. 그래서 다음처럼 줄일 수도 있다.

• 중앙이 5가 아니면 바로 false 를 반환한다.
• 첫 행 합과 비교하지 않고 모든 합을 15와 바로 비교한다.

배운 점

• 문제의 조건이 입력에 대한 것인지 정답에 대한 것인지 구분해서 읽어야 한다.
• 집합의 크기가 9인지만 보면 서로 다르다는 것만 알 수 있다. 값의 범위는 따로 확인해야 한다.