[Leetcode] 36. Valid Sudoku_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '36. Valid Sudoku'에 대해서 살펴보고자 합니다.

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해 준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Valid Sudoku' 알고리즘 문제

 

STEP 2. 'Valid Sudoku' 코드(code)

 

STEP 3. 'Valid Sudoku' 해설

 

STEP 4. 'Valid Sudoku' solution

 

반응형

 

STEP 1. '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:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
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.

---

9 x 9 스도쿠 보드가 유효한지 확인합니다. 다음 규칙에 따라 채워진 셀만 검증하면 됩니다.

각 행에는 1~9의 숫자가 반복 없이 포함되어야 합니다.
각 열에는 1~9의 숫자가 반복 없이 포함되어야 합니다.
그리드의 9개의 3 x 3 하위 상자 각각에는 숫자 1-9가 반복 없이 포함되어야 합니다.

메모:
스도쿠 보드(부분적으로 채워짐)는 유효할 수 있지만 반드시 풀 수 있는 것은 아닙니다.
언급된 규칙에 따라 채워진 셀만 유효성을 검사하면 됩니다.

 

Constraints:

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

---

STEP 2. 'Valid Sudoku' 코드(code)

 

■ Runtime: 93ms Beats 50.91%
■ Memory: 16.50MB Beats 87.95%

 

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        '''Row Area'''
        for row in board:
            hash_row = {}
            for value_r in row:
                if value_r != '.' :               
                    if (value_r not in hash_row):
                        hash_row[value_r] = 1
                    else :
                        return False

        '''Column Area'''
        for col in range(9):
            hash_column = {}
            for row in range(9):
                value_c = board[row][col]
                if value_c != '.':
                    if (value_c not in hash_column):
                        hash_column[value_c] = 1
                    else :
                        return False

        '''Square Area'''
        for i in [[0,1,2], [3,4,5], [6,7,8]]:
            for j in [[0,1,2], [3,4,5], [6,7,8]]:
                hash_square = {}
                for r in i:
                    for c in j :
                        check = board[r][c]
                        if check != '.':
                            if (check not in hash_square):
                                hash_square[check] = 1

                            else:
                                return False
        return True

 

---

STEP 3. 'Valid Sudoku' 해설

 

행 (row), 열 (column) 그리고 3x3 스도쿠 영역 (square)을 순회하면서, 각 조건 별 hash table (_hash)에 온점 (.)이 아닌 경우에 hash에 저장하고, 만약에 1번 더 나올 경우 False를 반환하는 방식입니다.

 

모든 조건을 다 조회하는 방식이기에, solution에서는 최적의 조건을 중심으로 검토해 봤습니다.

 

 

STEP 4. 'Valid Sudoku' solution

 

추가적으로, Leetcode에서 제공해 준 solution 코드를 살펴보겠습니다.

 

■ Runtime: 93ms Beats 50.91%
■ Memory: 16.52MB Beats 55.80%

 

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = defaultdict(set)
        cols = defaultdict(set)
        boxes= defaultdict(set)

        for r in range(9):
            for c in range(9):
                if board[r][c] == '.' : continue

                if (board[r][c] in rows[r]) or (board[r][c] in cols[c]) or (board[r][c] in boxes[(r//3, c//3)]):
                    return False
                
                rows[r].add(board[r][c])
                cols[c].add(board[r][c])
                boxes[(r//3, c//3)].add(board[r][c])

        return True

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '36. Valid Sudoku'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.