[LeetCode] 36. Valid Sudoku

문제 링크 >> https://leetcode.com/problems/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:

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.

 

 

👉 입출력

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.

 

 

📝 풀이

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # row, col
        for i in range(9):
            row = list(filter(lambda x: x.isalnum(),board[i]))
            if len(row) != len(set(row)):
                return False
            
            col = []
            for j in range(9):
                col.append(board[j][i])
            col = list(filter(lambda x: x.isalnum(),col))
            if len(col) != len(set(col)):
                return False
            
        # box
        for i in range(3):
            for j in range(3):
                box = []
                for k in range(3):
                    for l in range(3):
                        box.append(board[3*i+k][3*j+l])
                box = list(filter(lambda x: x.isalnum(),box))
                if len(box) != len(set(box)):
                    return False
        return True

 

각 구역을 살펴보며 빈 공간인 "."은 제거하고 숫자들만 남긴다.

그리고 리스트의 길이와 set으로 변환한 것의 길이를 비교해 중복이 있는지 확인한다.

만약 중복된 숫자가 있으면 유효한 스도쿠가 아니기 때문에 바로 False를 리턴한다.

row, col, box의 세 가지 경우에서 모두 False를 리턴하지 않았다면 유효한 스도쿠 이므로 True를 리턴한다.