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