Leetcode 36. Valid Sudoku with Python

Alpha, Orderly·2023년 1월 17일
0

leetcode

목록 보기
36/140
post-thumbnail

문제

Determine if a 9 x 9 Sudoku board is valid. 

주어진 9 * 9 스도쿠가 성립하는지 검사하시오
'.' 은 빈 스도쿠를 의미한다.

예시

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

제한

board.length == 9
board[i].length == 9
board[i][j] 의 원소는 숫자 혹은 '.' 이다.

문제 구연설명

본 문제는 완벽한 스도쿠가 형성되었는가를 묻는게 아닌,
모든 숫자가 한 Column, Row, Box에서 중복되지 않는가를 검사하는 것이다.

풀이법

그렇기에 빈칸이 아닌 숫자가 중복되지 않는지를 검사하면 된다.

나는 Set을 이용하였는데, Row-Column-Box 각각의 Set을 만들어 안에 값이 있는지를 먼저 검사한다.

만약 값이 있다면 중복되었다는 것으로 False 리턴, 아니면 Set에 값을 넣는다.

이 과정을 각 3개의 제한 조건에 실행하면 된다.

def checkcorrect(board: List[List[str]], row, col):
    c = set()
    r = set()
    b = set()
    for i in board[row]:
        if i == '.': continue
        if i in r: return False
        r.add(i)
    for j in range(9):
        if board[j][col] == '.': continue
        if board[j][col] in c: return False
        c.add(board[j][col])
    trow = (row // 3) * 3
    tcol = (col // 3) * 3
    for i in range(trow, trow + 3):
        for j in range(tcol, tcol + 3):
            if board[i][j] == '.': continue
            if board[i][j] in b: return False
            b.add(board[i][j])
    return True

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        for i in range(9):
            for j in range(9):
                if board[i][j] != '.' and checkcorrect(board, i, j) == False: return False
        return True
profile
만능 컴덕후 겸 번지 팬

0개의 댓글