[leetcode-36] Valid Sudoku

LeetCode-36

Valid Sudoku : A Sudoku board (partially filled) could be valid but is not necessarily solvable.

note : Only the filled cells need to be validated according to the mentioned rules.

Answer

        :::python

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        def valid_row(i, j, row):
            if row==1:
                item = board[i]
            else:
                item = [board[n][j] for n in range(0,9)]
            p = []
            box = [board[i//32 + r][j//32 + c] for r in range(i//3, i//3+3) for c in range(j//3, j//3+3)]    
            b = []
            for i in range(0,9):
                if item[i] !='.':
                    p.append(item[i])
                if box[i] !='.':
                    b.append(box[i])
            if len(set(box))-1 == len(b):
                pass 
            else:
                return False
            if len(set(item))-1 == len(p):
                return True 
            else: 
                return False
        for i in range(0,9):
            for j in range(0,9):
                if valid_row(i,j,0) and valid_row(i,j,1):
                    pass
                else:
                    return False
        return True

Result : 272ms Memory: 16.5mb

문제: 유효한 스도쿠

이 문제는 9x9 크기인 스도쿠 게임이 유효한지 확인하는 문제입니다. 각 행, 열, 그리고 작은 3x3 사각형에 1~9의 숫자가 한 번씩만 등장하면 유효한 스도쿠입니다. 입력으로 이를 나타내는 9x9 문자열 배열이 주어집니다.

해결책:

이 문제의 핵심은 각 행, 열, 사각형에 중복된 숫자가 있는지를 확인하는 것입니다. 우리는 각 행, 열, 그리고 작은 사각형을 9개씩 총 27개의 그룹으로 나눌 수 있습니다. 이 그룹들 중 한 그룹에 중복된 숫자가 있다면 스도쿠는 유효하지 않습니다.

따라서, 각 그룹의 중복 여부를 체크하는 helper function valid_row 를 만들고 이 함수를 이용해서 각 행, 열, 작은 사각형에 대해 유효성을 판단할 수 있습니다.

valid_row 함수에는 3개의 인자가 필요합니다. i 와 j 는 현재 검사하고 있는 원소의 위치를 나타냅니다. row 는 0, 1로 나눌 수 있으며, 각각 해당 원소의 행과 열을 검사하는 경우입니다.

함수는 해당 그룹에 속한 모든 원소를 모은 item 리스트와 같은 작은 사각형에 속한 모든 원소를 모은 box 리스트를 만듭니다. item 과 box 리스트에서 . 를 제외한 모든 원소를 p 와 b 리스트에 저장합니다.

그리고나서 set 을 이용해서 중복된 숫자가 있는지 확인합니다. 만약 중복된 숫자가 있다면, 해당 그룹이 유효하지 않습니다. 마지막으로, 해당 그룹이 유효하다면 True 를 반환합니다.

그리고 isValidSudoku 메소드는 각 행, 열, 작은 사각형에 대해서 valid_row 함수를 호출하기만 하면 됩니다.

이렇게 작성한 해결책의 시간복잡도는 $O(81 \times (3 \times 9)) = O(2187)$ 이므로 충분히 효율적입니다.

아래는 주어진 코드입니다.

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        def valid_row(i, j, row):
            if row==1:
                item = board[i]
            else:
                item = [board[n][j] for n in range(0,9)]
            p = []
            box = [board[i//3*3 + r][j//3*3 + c] for r in range(0,3) for c in range(0,3)]    
            b = []
            for i in range(0,9):
                if item[i] !='.':
                    p.append(item[i])
                if box[i] !='.':
                    b.append(box[i])
            if len(set(box))-1 == len(b):
                pass 
            else:
                return False
            if len(set(item))-1 == len(p):
                return True 
            else: 
                return False
        for i in range(0,9):
            for j in range(0,9):
                if valid_row(i,j,0) and valid_row(i,j,1):
                    pass
                else:
                    return False
        return True

코드 리뷰:

주어진 코드는 위에서 정의한 해결책과 굉장히 유사합니다.

다만, 작은 사각형에 대한 box 를 만들 때 잘못된 인덱싱을 사용하는 오류가 있습니다. box 의 원소의 인덱스를 찾을 때에는 3을 곱해야 하는데 2로 찾게 되어서 문제가 생깁니다.

올바른 코드:

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        def valid_row(i, j, row):
            if row==1:
                item = board[i]
            else:
                item = [board[n][j] for n in range(0,9)]
            p = []
            box = [board[i//3*3 + r][j//3*3 + c] for r in range(0,3) for c in range(0,3)]    
            b = []
            for i in range(0,9):
                if item[i] !='.':
                    p.append(item[i])
                if box[i] !='.':
                    b.append(box[i])
            if len(set(box))-1 == len(b):
                pass 
            else:
                return False
            if len(set(item))-1 == len(p):
                return True 
            else: 
                return False
        for i in range(0,9):
            for j in range(0,9):
                if valid_row(i,j,0) and valid_row(i,j,1):
                    pass
                else:
                    return False
        return True