[LeetCode][Python3] 36. Valid Sudoku

Problem :

https://leetcode.com/problems/valid-sudoku

My Solution :

class Solution:

def isValidSudoku(self, board):

"""

:type board: List[List[str]]

:rtype: bool

"""

def vaildate(lis):

nums = [x for x in lis if x != '.']

return len(set(nums)) == len(nums)

for row in board:

if not vaildate(row):

return False

for col in zip(*board):

if not vaildate(col):

return False

for i in range(0, 7, 3):

for j in range(0, 7, 3):

square = [x for row in board[i:i+3] for x in row[j:j+3]]

if not vaildate(square):

return False

return True

Comment :

일단 처음 문제를 접했을 때 당연히 Brute Force를 생각할 수 밖에 없었다. 행을 먼저 검증하고 열을 검증한 다음 마지막으로 3x3 작은 정사각형 9개를 검증하였다.

아래는 set을 활용하여 1pass에 검증하는 방법이다. (행, 값), (값, 열), (행//3, 열//3, 값) 이 기존에 등장했는지 검증하고 set에 추가한다. (행//3, 열//3, 값) 검증은 3x3 작은 정사각형 단위로 중복 등장 여부를 검증하는 것이다. (아래 검증이 문제 없는 이유는 값이 str이고 행, 열은 int이기 때문이다. 즉 (3, "5")와 ("3", 5)는 다르다.)

My Solution2 :

class Solution:

def isValidSudoku(self, board):

"""

:type board: List[List[str]]

:rtype: bool

"""

already = set()

for i in range(9):

for j in range(9):

c = board[i][j]

if c != '.':

if ((i, c) in already or

(c, j) in already or

(i//3, j//3, c) in already):

return False

already.add((i, c))

already.add((c, j))

already.add((i//3, j//3, c))

return True