A-007● Day 072026.05.09mediumleetcode #36neetcode150

유효한 스도쿠

#array#hash-table#matrix

문제

· problem

P.007

유효한 스도쿠

9 x 9 스도쿠 보드가 유효한지 판단하시오. 채워진 셀만 다음 규칙에 따라 유효성을 검사하면 됩니다: 각 행은 1-9의 숫자를 중복 없이 포함해야 합니다. 각 열은 1-9의 숫자를 중복 없이 포함해야 합니다. 9개의 3 x 3 부분 박스 각각은 1-9의 숫자를 중복 없이 포함해야 합니다. 참고: 스도쿠 보드는 부분적으로 채워질 수 있으며 유효하지만 해결 불가능할 수 있습니다. 채워진 셀만 위의 규칙에 따라 검사하면 됩니다.

제약

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

// 지문은 본인 언어 요약 — 원문은 위 링크에서

입출력 예시

example 1input → output

[["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"]]

true

example 2input → output

[["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"]]

false

사전 사고

· pre-solve

● 1리스트 출력→● 2선택→● 3정답 공개

☐
세 가지 규칙(행, 열, 3x3 박스)을 모두 동시에 검사해야 합니까?
☐
'채워진 셀만 검사'라는 것은 정확히 무엇을 의미합니까?
☐
숫자가 같은 행에 두 번 나타나면 보드는 자동으로 유효하지 않습니까?
☐
입력 보드가 항상 정확히 9x9라고 가정할 수 있습니까?
☐
충돌이 발생한 셀을 반환해야 합니까?
☐
스도쿠 보드가 풀 수 있는지 확인해야 합니까?

던질 질문에 체크하고 확인을 누르세요

// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)

논리 구조

· logic

● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개

// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.

step 1· 추적 구조 초기화

○

cols = collections.defaultdict(set)

○

cols = {}

○

cols = set()

step 2· 모든 셀을 반복

○

for r in range(9):

○

for r in range(8):

○

for row in board:

step 3· 빈 셀 건너뛰기│ │ 중첩

○

if board[r][c] == ".":

○

if board[r][c] == 0:

○

if not board[r][c]:

step 4· 충돌 확인│ │ 중첩

○

board[r][c] in rows[r]

○

board[r][c] == rows[r]

○

rows[r].get(board[r][c])

step 5· 셀을 3x3 박스로 매핑│ │ 중첩

○

or board[r][c] in squares[(r // 3, c // 3)]

○

squares[(r // 2, c // 2)]

○

squares[(r % 3, c % 3)]

step 6· 본 값 추적│ │ 중첩

○

cols[c].add(board[r][c])

○

cols[c].append(board[r][c])

○

cols[c] = {board[r][c]}

각 슬롯에 한 줄씩 골라보세요

// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.

문제풀이 · 트레이스

· solve

solution.py

class Solution:

    def isValidSudoku(self, board: List[List[str]]) -> bool:

        cols = collections.defaultdict(set)

        rows = collections.defaultdict(set)

        squares = collections.defaultdict(set)  # key = (r /3, c /3)

        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

                cols[c].add(board[r][c])

                rows[r].add(board[r][c])

                squares[(r // 3, c // 3)].add(board[r][c])

        return True

머릿속 dry-run 케이스

// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.

case 1

[["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"]]

→

true

case 2

[["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"]]

→

false

// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.