Leetcode Python - 36. Valid Sudoku

Leetcode #36 - Valid Sudoku

이번에는 특정 챕터별로 문제들을 풀어보겠습니다. string을 집중적으로 풀어보겠습니다.

리트코드의 문제 36 ‘Valid Sudoku’을 파이썬으로 풀어 보도록 하겠습니다.

이번에도 시간내로 구현이 어려워 discuss를 보도록 하겠습니다. 포인트는 set의 성질을 이용하는 것과 가로, 세로, 3x3으로 쪼개어 validation하는 것입니다.

전체 코드는 아래와 같습니다.

class Solution:
    def isValidSudoku(self, board):
        return (self.is_row_valid(board) and
                self.is_col_valid(board) and
                self.is_square_valid(board))
        
    def is_row_valid(self, board):
        for row in board:
            if not self.is_unit_valid(row):
                return False
        return True

    def is_col_valid(self, board):
        for col in zip(*board):
            if not self.is_unit_valid(col):
                return False
        return True
        
    def is_square_valid(self, board):
        for i in (0,3,6):
            for j in (0,3,6):
                square = [board[x][y] for x in range(j,j+3) for y in range(i,i+3)]
                if not self.is_unit_valid(square):
                    return False
        return True

    def is_unit_valid(self, unit):
        unit = [i for i in unit if i != '.']
        return len(set(unit)) == len(unit)

시간복잡도는 O(n^4)

• row case : n*n
• col case : n*n
• square case : n/3n/3n/3*n/3

공간복잡도는 O(n^2) : 한번에 최대로 담는 상수는 row, col, square

• row : n
• col : n
• square : n/3*n/3