matrix 문제 2. nxn filtering
matrix 문제 2. nxn filtering — #LeetCode #개발자의도구들 #nxn필터링 only 파이썬 목표 참고 : 여기 전략 생각하기 오답이다 ❌ cell ...
#LeetCode#Naver Blog
#LeetCode #개발자의도구들 #nxn필터링
- only 파이썬
- 목표 참고 : 여기
전략 생각하기
LeetCode(medium 36. Valid Sudoku) 61.8%
🤔 Brute Force?
>>> O(9*9) * 3번 1
>>>> O(1)
class Solution(object):
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
rowCheck = True
colCheck = True
cellCheck = True
n = len(board[0])
# O( 9 * 9)
# row check
for i in range(n):
row = set()
for j in range(n):
test = board[i][j]
if test == ".":
continue
if test not in row:
row.add(test)
else:
rowCheck = False
break
print("row, rc: {}, {}".format(row, rowCheck))
# col check
for i in range(n):
col = set()
for j in range(n):
test = board[j][i]
if test == ".":
continue
if test not in col:
col.add(test)
else:
colCehck = False
break
print("col, cc: {}, {}".format(col, colCheck))
# cesll check
for k in range(1, 4):
# 1 2 3
for i in range(k * 3):
cell = set()
for l in range(1, 4):
for j in range(l * 3 - 3, l * 3):
print("{}, {}".format(i, j))
test = board[i][j]
if test == ".":
continue
if test not in cell:
cell.add(test)
else:
cellCheck = False
break
print("cel, cc: {}, {}".format(cell, cellCheck))
return rowCheck and colCheck and cellCheck
- 오답이다 ❌
- cell 갱신이, row와 col에 영향을 받아서 구분하기가 어렵다.
- 그냥 row를 3개씩 끊어서 계산하는 것이 편해보인다.
Cell filtering
Cell을 구분하는데서 많은 시행착오가 발생했다. 이 문제의 핵심이 여기라고 생각된다.
🙄 난해하다.
✅ while으로 돌려보자.
>>> 조건에 따라 row와 col count를 증가시키는 방향으로
class Solution(object):
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
rowCheck = True
colCheck = True
cellCheck = True
n = len(board[0])
# O( 9 * 9)
# row check
for i in range(n):
row = set()
for j in range(n):
test = board[i][j]
if test == ".":
continue
if test not in row:
row.add(test)
else:
print("row fail")
return False
# col check
for i in range(n):
col = set()
for j in range(n):
test = board[j][i]
if test == ".":
continue
if test not in col:
col.add(test)
else:
print("col fail ")
return False
rc = 0
cc = 0
# cell check
invalid = False
while 1:
if rc >= 3 or invalid:
break
cell = set()
for i in range(rc * 3, rc * 3 + 3):
if invalid == True:
break
for j in range(cc * 3, cc * 3 + 3):
test = board[i][j]
if test == ".":
if i == rc * 3 + 2 and j == cc * 3 + 2: # reach the last
cc += 1
break
continue
if test not in cell:
cell.add(test)
else:
print("cell fail")
return False
if i == rc * 3 + 2 and j == cc * 3 + 2: # reach the last
cc += 1
if cc == 2:
rc += 1
cc = 0
return True
- 오답이다
- 조건부에 맞춰서 i와 j값을 조정하는 것은 가능했다.
- 하지만 특정 예시에서 오답이 나온다.
- 다른 건 문제없고 아마 cell쪽에서 오류가 나오는 것이다.
🙄 error case
[[".","2",".",".",".",".",".",".","."],
[".",".",".",".",".",".","5",".","1"],
[".",".",".",".",".",".","8","1","3"], 👉 여기를 못찾아낸다. 🤔 문제가 무엇일까...
["4",".","9",".",".",".",".",".","."],
[".",".",".",".",".",".",".",".","."],
[".",".","2",".",".",".",".",".","."],
["7",".","6",".",".",".",".",".","."],
["9",".",".",".",".","4",".",".","."],
[".",".",".",".",".",".",".",".","."]]
최종 코드
👉 문제 발견
>>> cc += 1이후 바로 cc == 2 확인을 하는 바람에 j열 6,7,8을 검증하지 못했다.
✅ 각 포인터를 어떻게
class Solution(object):
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
rowCheck = True
colCheck = True
cellCheck = True
n = len(board[0])
# O( 9 * 9)
# row check
for i in range(n):
row = set()
for j in range(n):
test = board[i][j]
if test == ".":
continue
if test not in row:
row.add(test)
else:
print("row fail")
return False
# col check
for i in range(n):
col = set()
for j in range(n):
test = board[j][i]
if test == ".":
continue
if test not in col:
col.add(test)
else:
print("col fail ")
return False
rc = 0
cc = 0
# cell check
invalid = False
while 1:
if rc >= 3 or invalid:
break
cell = set()
for i in range(rc * 3, rc * 3 + 3):
if invalid == True:
break
for j in range(cc * 3, cc * 3 + 3):
test = board[i][j]
if test == ".":
if i == rc * 3 + 2 and j == cc * 3 + 2: # reach the last
cc += 1
break
continue
if test not in cell:
cell.add(test)
else:
return False
if i == rc * 3 + 2 and j == cc * 3 + 2: # reach the last
cc += 1
if cc > 2:
rc += 1
cc = 0
return True
- t: O(1) 83.88% Beats
- s: O(1) 86.67% Beats
- GPT 안보고 끝까지 꾸역 꾸역 풀어서 뿌듯함...
- 근데 예외는 참고했어서 아쉽다...