[leetcode] 49. Group Anagrams ํ์ด, ํด์ค (python)
๋ฌธ์ ๋งํฌ
https://leetcode.com/problems/valid-sudoku/
Valid Sudoku - LeetCode
Can you solve this real interview question? 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 c
leetcode.com
์ค๋์ฟ ๊ฐ ์ ํจํ์ง ํ์ธํ๋ ๋ฌธ์ ์ด๋ค.
์์ ํ ์ค๋์ฟ ์ ๊ท์น์ ๋ชจ๋ ์ฒดํฌํ์ง๋ ์๊ณ , ๊ฐ๋ก, ์ธ๋ก, 3*3์ ์ค๋ณต๋ ๊ฐ์ด ์๋์ง ์๋์ง๋ง ์ฒดํฌํ๋ฉด ๋๋ค.
1์ฐจ ํ์ด
๋ฉ์๊ฒ ํ๊ณ ์ถ์์ง๋ง, ์๊ฐ์ ๊ฐ๋ก,์ธ๋ก,3*3์ ๊ฐ๊ฐ for๋ฌธ์ ๋๋ ค์ ํ์ธํ๋ ํ์ด๋ก ์ ๊ทผํ๋ค.
(์๋ 2์ฐจ ํ์ด๋ก ์ค๋ช ํ๊ฒ ์ง๋ง, ์ด์ค for๋ฌธ ํ๋๋ก ๋ชจ๋ ๊ฒ์ ํด๊ฒฐํ ์ ์๋ ๋์ด์คํ ํ์ด๊ฐ ์๋ค. )
๊ฐ๋ก์ ์ธ๋ก๋ ๋น๊ต์ ๋จ์ํ์ง๋ง, 3*3์ ์ฒดํฌํ๋ ๋ก์ง์ด ๊น๋ค๋ก์ ๋๋ฐ,
์ด ๋ถ๋ถ์ ์ค๊ฐ์ขํ๋ฅผ ๊ธฐ์ค์ผ๋ก x -1,0,1 y -1,0,1์ ํด์ ๊ตฌํ๋ ๋ก์ง์ผ๋ก ํ๋ค.
๊ทธ ๊ณผ์ ์์ 4์ค for๋ฌธ์ ์จ๋ฒ๋ ธ๋ค ;;
class Solution(object):
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
# ๊ฐ๋ก์ค ํ์ธ
for row in board :
checks = set()
for w in row :
if w != '.' and w in checks:
return False
checks.add(w)
# ์ธ๋ก์ค ํ์ธ
for c in range(9) :
checks = set()
for row in board:
if row[c] != '.' and row[c] in checks:
return False
checks.add(row[c])
# 3 * 3 ํ์ธ : ์ค์ฌ ์ขํ ๊ธฐ์ค์ผ๋ก ํ์ธ
for x in range(1,8,3):
for y in range(1,8,3) :
checks = set()
for dx in range(-1,2):
for dy in range(-1,2):
if board[x + dx][y + dy] != '.' and board[x + dx][y + dy] in checks:
return False
checks.add( board[x + dx][y + dy])
return True
์ดํ ๋ฐ๋ก O(9*9), for๋ฌธ ํ๋๋ก ํ ์ ์๋ ํ์ด๋ฅผ ์ค๋ช ํ๊ฒ ๋ค.
2์ฐจ ํ์ด (ํด์ค ์ฐธ๊ณ )
ํด๋น ํ์ด๋ ์๋ ์ ํฌ๋ธ๋ฅผ ์ฐธ๊ณ ํ๋ค.
https://www.youtube.com/watch?v=TjFXEUCMqI8
์ด ๋ฐฉ์์ for๋ฌธ์ ๋๋ฉด์, ๊ฐ๋ก,์ธ๋ก,์ฌ๊ฐํ์ ๋ชจ๋ ํ์ธํ๋ฉด์ ์ค๋ณต์ด ์๋์ง ํ์ธ ๋ฐ ๊ฐ์ ์ธํ ํด์ฃผ๋ ๋ถ๋ถ์ด๋ค.
๋์ฌ๊ฒจ๋ด์ผ ํ๋ ๋ถ๋ถ์ ์ฌ๊ฐํ ์ฒดํฌ ๊ฐ์ ๊ฒฝ์ฐ ์๋ ์ขํ์์ ๋ชจ๋ ๋์ผํ ํค ๊ฐ์ ์ค์ ํ๊ธฐ ์ํด์ (r // 3, c // 3)์ผ๋ก ์ค์ ํ ๋ถ๋ถ์ด๋ค.
(0,0) (0,1) (0,2)
(1,0) (1,1) (1,2)
(2,0) (2,1) (2,2)
rows = defaultdict(set)
cols = defaultdict(set)
squares = 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 squares[(r//3,c//3)]):
return False
rows[r].add(board[r][c])
cols[c].add(board[r][c])
squares[(r//3,c//3)].add(board[r][c])
return True