문제 링크 >> https://leetcode.com/problems/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.
👉 입출력
Example 1:
Input: 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"]]
Output: true
Example 2:
Input: 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"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8.
Since there are two 8's in the top left 3x3 sub-box, it is invalid.
📝 풀이
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
# row, col
for i in range(9):
row = list(filter(lambda x: x.isalnum(),board[i]))
if len(row) != len(set(row)):
return False
col = []
for j in range(9):
col.append(board[j][i])
col = list(filter(lambda x: x.isalnum(),col))
if len(col) != len(set(col)):
return False
# box
for i in range(3):
for j in range(3):
box = []
for k in range(3):
for l in range(3):
box.append(board[3*i+k][3*j+l])
box = list(filter(lambda x: x.isalnum(),box))
if len(box) != len(set(box)):
return False
return True
각 구역을 살펴보며 빈 공간인 "."은 제거하고 숫자들만 남긴다.
그리고 리스트의 길이와 set으로 변환한 것의 길이를 비교해 중복이 있는지 확인한다.
만약 중복된 숫자가 있으면 유효한 스도쿠가 아니기 때문에 바로 False를 리턴한다.
row, col, box의 세 가지 경우에서 모두 False를 리턴하지 않았다면 유효한 스도쿠 이므로 True를 리턴한다.
'Algorithm > Python' 카테고리의 다른 글
[백준 22862번] 가장 긴 짝수 연속한 부분 수열 (large) (0) | 2022.05.14 |
---|---|
[백준 21921번] 블로그 (0) | 2022.05.10 |
[백준 14425번] 문자열 집합 (0) | 2022.04.17 |
[백준 1966번] 프린터 큐 (0) | 2022.04.15 |
[백준 2263번] 트리의 순회 (0) | 2022.04.14 |
댓글