[DSA][Array & Hashing] 07. Valid Sudoku

LeetCode 36

 

07. 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.

 

 

[질문하기]

- board의 가로, 세로는 9로 고정인가요?

- 빈칸은 무시하고 숫자로 채워진 칸만 검증하면 되나요?

 

 

[아이디어]

중복을 처리하는데 효율적인 자료구조인 set을 사용하자.

가로, 세로, Sub 네모의 중복을 판단하면 된다.

 

 

[풀이 1] hash, set

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        ROW = defaultdict(set)
        COL = defaultdict(set)
        REC = defaultdict(set)

        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    continue
                if board[r][c] in ROW[r] or board[r][c] in COL[c] or board[r][c] in REC[3*(r//3) + c//3]:
                    return False
                ROW[r].add(board[r][c])
                COL[c].add(board[r][c])
                REC[3*(r//3) + c//3].add(board[r][c])
            
        return True

0부터 8까지의 ROW, 0부터 8까지 COL에 대해 원소를 set에 저장하면 중복 여부를 빠르게 판단할 수 있다.

각 네모에 대해서 인덱스를 만드는 게 살짝 어려울 수 있는데, 행과 열을 이용해서 아래의 그림과 같이 KEY를 만들 수 있다.

네모 한칸이 하나의 KEY로 식별될 수 있어야 하기 때문에 0 ~ 2 / 3 ~ 5 / 6 ~ 8이 하나의 수로 grouping이 되어야 한다.

그래서 3으로 나눈 몫을 구하면 각자 0, 1, 2에 mapping이 되고, 이것을 이용하여 (r//3, c//3) 자체를 key로 이용하거나, 3 * r // 3 + c // 3으로 0 ~ 8로 다시 mapping을 시켜서 KEY로 이용할 수도 있다.

 

⏱️ 시간복잡도

이차원 배열을 한번 순회하기 때문에 O(n^2)

🧠 공간복잡도

board의 원소 개수만큼의 공간이 필요하므로 O(n^2)