36. Valid Sudoku

1. Description

• Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. 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.

2. Example

Example 1

**Input:** board = 

[[“5”,“3”,”.”,”.”,“7”,”.”,”.”,”.”,”.”] ,[“6”,”.”,”.”,“1”,“9”,“5”,”.”,”.”,”.”] ,[”.”,“9”,“8”,”.”,”.”,”.”,”.”,“6”,”.”] ,[“8”,”.”,”.”,”.”,“6”,”.”,”.”,”.”,“3”] ,[“4”,”.”,”.”,“8”,”.”,“3”,”.”,”.”,“1”] ,[“7”,”.”,”.”,”.”,“2”,”.”,”.”,”.”,“6”] ,[”.”,“6”,”.”,”.”,”.”,”.”,“2”,“8”,”.”] ,[”.”,”.”,”.”,“4”,“1”,“9”,”.”,”.”,“5”] ,[”.”,”.”,”.”,”.”,“8”,”.”,”.”,“7”,“9”]] Output: true

Example 2

**Input:** board = 

[[“8”,“3”,”.”,”.”,“7”,”.”,”.”,”.”,”.”] ,[“6”,”.”,”.”,“1”,“9”,“5”,”.”,”.”,”.”] ,[”.”,“9”,“8”,”.”,”.”,”.”,”.”,“6”,”.”] ,[“8”,”.”,”.”,”.”,“6”,”.”,”.”,”.”,“3”] ,[“4”,”.”,”.”,“8”,”.”,“3”,”.”,”.”,“1”] ,[“7”,”.”,”.”,”.”,“2”,”.”,”.”,”.”,“6”] ,[”.”,“6”,”.”,”.”,”.”,”.”,“2”,“8”,”.”] ,[”.”,”.”,”.”,“4”,“1”,“9”,”.”,”.”,“5”] ,[”.”,”.”,”.”,”.”,“8”,”.”,”.”,“7”,“9”]] Output: false Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8’s in the top left 3x3 sub-box, it is invalid.

3. Solution

• Runtime: 0ms
• 설명
  • 이 문제는 내가 $O(N^2)$를 너무 생각해서 for문을 두번 돌리는걸 생각을 안하고 풀려고 했더니 못풀었다.
  • 답지를 보고 이해하며 Chat GPT를 보고 코드 분석을 진행했다.
  • 행(row), 열(column), $3\times 3$ 박스(box)를 저장할 자료구조 생성한다.
  • $9\times 9$ 스도쿠 보드에 .(빈 칸)이면 건너뛴다.
  • if board[r][c] in rows[r] or board[r][c] in cols[c] or board[r][c] in boxes[(r //3, c//3)]:
    • 숫자가 중복되는지 검사한다.
  • 중복이 아니라면 숫자를 저장한다.

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = defaultdict(set)
        cols = defaultdict(set)
        boxes = 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 boxes[(r //3, c//3)]:
                    return False
 
                rows[r].add(board[r][c])
                cols[c].add(board[r][c])
                boxes[(r // 3, c // 3)].add(board[r][c])
            
        return True

• 📌defaultdict란?
  • 모든 Key에 대해 기본(default) 값을 설정해준다.
  • defaultdict(set)이면
    • 딕셔너리 Key값을 set을 default 값으로 지정한다는 것이다.
• ✏️내가 이해하지 못했던 부분
  • 숫자 저장이 필요한 이유
    • 중복되는 숫자가 없어야 하기 때문에 이미 등장한 숫자를 저장하여 중복이 발생하는지 빠르게 확인하기 위해 set를 사용하여 확인한다.

4. What I Learned

References

• Chat GPT
• defaultdict 관련 블로그