[LeetCode 해석 및 풀이] 36. Valid Sudoku

LeetCode 문제 해석 및 풀이 방법

 

문제 36. Valid Sudoku(유효한 스도쿠)

바로가기

 

문제 설명

영문

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

 

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

 

Note:

• A Sudoku board (partially filled) could be valid but is not necessarily solvable.
• Only the filled cells need to be validated according to the mentioned rules.

 

한글

9x9 스도쿠가 유효한지 결정하세요. 채워진 칸만 해당 규칙에 따라 검증해주면 됩니다.

 

1. 각 행은 반드시 1-9사이의 수를 반복없이 포함하여야 합니다
2. 각 열은 반드시 1-9사이의 수를 반복없이 포함하여야 합니다.
3. 각 9개의 3x3 작은 상자들은 반드시 1-9사이의 수를 반복없이 포함하여야 합니다.

 

노트:

• 스도쿠(부분적으로 채워진)들은 유효하여야 하지만 풀이 가능 여부는 상관없습니다.
• 오직 채워진 칸만 위 규칙에 따라 검증합니다.

 

제한조건

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit 1-9 or '.'.

 

입출력 예

입력	출력
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"]]	true
board =  [["8","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"]]	false

 

해답 및 해설

파이썬 (Python)

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        def isDuplicated(nums: List[str])->bool:
            num_set = set()
            for num in nums:
                if num == ".": continue
                if num in num_set: return True
                num_set.add(num)
            return False
        
        for horiz_num in range(9):
            horiz_line = board[horiz_num]
            if isDuplicated(horiz_line): return False
        
        for verti_num in range(9):
            verti_line = [x[verti_num] for x in board]
            if isDuplicated(verti_line): return False

        for x in range(0,9,3):
            for y in range(0,9,3):
                sqare = [*(n for n in board[x][y:y+3]),
                *(n for n in board[x+1][y:y+3]),
                *(n for n in board[x+2][y:y+3]),
                ]
                if isDuplicated(sqare): return False
        
        return True

적당히 겹치는 숫자가 있는지 검증해주면 되는 문제. 겹치는 숫자를 체크해주는 isDuplicated라는 함수를 만든 후 각 행, 열, 사각형에 대해 검증해주었다.