[LeetCode | Python] 36. Valid Sudoku

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Note:
A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.

풀지 않아도 되고 검사만 하면 된다!

 

풀이 1: Brute Force

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:

        # row 검사
        for row in board:
            numSet = set()
            for c in range(0, 9):
                if row[c] == '.':
                    continue
                elif row[c] not in numSet:
                    numSet.add(row[c])
                else:
                    return False

        # col 검사
        for c in range(0, 9):
            numSet = set()
            for r in range(0, 9):
                if board[r][c] == '.':
                    continue
                elif board[r][c] not in numSet:
                    numSet.add(board[r][c])
                else:
                    return False

        # 3x3 검사
        for square in range(0, 9):
            numSet = set()
            for r in range(0, 3):
                for c in range(0, 3):
                    row = (square // 3) * 3 + r
                    col = (square % 3) * 3 + c
                    if board[row][col] == '.':
                        continue
                    elif board[row][col] not in numSet:
                        numSet.add(board[row][col])
                    else:
                        return False
        
        return True

 

시간 복잡도에 대한 제한은 없어서 브루트 포스를 생각했고, 3*3 검사가 젤 까다로운 부분이었다.

for square in range(0, 9) 로 하고 square를 3으로 나눈 몫과 나머지를 각각 row와 col 연산에 이용하면 된다.

이 문제에서는 Board 사이즈가 정해져 있었기 때문에, 시간 복잡도는 O(1)이다.

 

 

풀이 2: Hash Set (One Pass)

One Pass 방식의 Hash Set을 이용해서 풀 수 있다.

One Pass 방식은 데이터를 한번만 순회하며 조건을 체크하는 방식이다.

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = defaultdict(set)
        cols = defaultdict(set)
        squares = defaultdict(set)
        
        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    continue
                if (board[r][c] in rows[r] or board[r][c] in cols[c] or board[r][c] in squares[(r // 3, c // 3)]):
                    return False

                rows[r].add(board[r][c])
                cols[c].add(board[r][c])
                squares[(r // 3, c // 3)].add(board[r][c])

        return True

defaultdict를 사용하여, 각 키에 set이 할당되도록 한다. 

중첩 for 루프를 활용하여 모든 칸을 탐색하고, 

행, 열, square에 중복 숫자가 있으면 바로 False를 리턴한다.

모든 칸 검사를 통과하면 True를 반환한다.

 

square에서는 (r // 3, c // 3) 좌표를 키로 사용했는데, 아래와 같이 서브그리드가 구분된다.

(0,0) | (0,1) | (0,2)
---------------------
(1,0) | (1,1) | (1,2)
---------------------
(2,0) | (2,1) | (2,2)