유효한 스도쿠 (LeetCode 36): Python 풀이, 박스 인덱스, 엣지 케이스

유효한 스도쿠(LeetCode 36)는 부분적으로 채워진 9x9 보드를 주고, 채워진 칸이 스도쿠 규칙을 위반하는지 묻습니다. 퍼즐을 풀 필요는 없습니다. 각 행, 열, 3x3 박스에서 숫자가 반복되지 않는지만 확인하면 됩니다. 본 숫자를 담는 세 개의 집합으로 한 번만 순회하면 O(81)로, 이는 상수입니다.

문제

보드는 1부터 9까지의 숫자 또는 빈 칸을 나타내는 . 문자가 들어 있는 9x9 격자입니다. 채워진 칸이 다음 규칙을 따르면 true를 반환합니다:

• 각 행에 반복되는 숫자가 없습니다.
• 각 열에 반복되는 숫자가 없습니다.
• 각 3x3 박스에 반복되는 숫자가 없습니다.

보드는 해가 없어도 유효할 수 있습니다. 채워진 칸만 확인합니다.

접근법: 단위별 세 개의 집합

각 행, 각 열, 각 박스마다 본 숫자의 집합을 유지합니다. 채워진 모든 칸에 대해 세 집합 모두에서 해당 숫자를 확인하고, 처음 보는 숫자라면 추가합니다.

생각이 필요한 부분은 박스 인덱스뿐입니다. 행 r, 열 c에 있는 칸의 박스 번호는 (r // 3) * 3 + c // 3입니다. 이는 박스를 왼쪽에서 오른쪽으로, 위에서 아래로 0부터 8까지 세는 방식입니다.

def is_valid_sudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    for r in range(9):
        for c in range(9):
            ch = board[r][c]
            if ch == ".":
                continue
            b = (r // 3) * 3 + c // 3
            if ch in rows[r] or ch in cols[c] or ch in boxes[b]:
                return False
            rows[r].add(ch)
            cols[c].add(ch)
            boxes[b].add(ch)
    return True

추적

행 0의 열 0에 5가 있고 열 4에 또 다른 5가 있다고 가정해 봅시다. 첫 번째 5는 rows[0], cols[0], boxes[0]에 추가됩니다. 열 4에서 ch in rows[0] 검사가 참이므로 함수는 즉시 false를 반환합니다. 같은 박스나 열에 있는 동일한 숫자도 나머지 두 집합에서 같은 방식으로 잡힙니다.

복잡도

보드는 항상 9x9이므로 시간은 상수이고, 81번의 칸 방문입니다. n x n 보드로 일반화하면 시간은 O(n 제곱), 공간은 O(n 제곱)입니다. 면접관이 확장성을 자주 묻기 때문에 둘 다 언급하세요.

면접관이 묻는 변형

비트마스크 버전은 각 집합을 정수로 대체합니다. mask & (1 << d)는 숫자를 검사하고 mask |= 1 << d는 기록합니다. 더 빠르지만, 시간 압박 속에서는 집합 버전이 정확하게 작성하기 더 쉽기 때문에 먼저 그것을 작성하세요.

흔한 실수

• 행과 열은 확인하지만 박스를 잊는 경우.
• r // 3 + c // 3처럼 잘못된 박스 공식으로, 서로 다른 박스에 같은 인덱스를 부여하는 경우.
• .을 숫자로 취급해서 두 빈 칸을 반복으로 세는 경우.
• 문제가 유효성만 묻는데 보드를 풀려고 하는 경우.

테스트할 엣지 케이스

면접에서 설명하는 방법

1. 규칙을 다시 말하고 풀지 않고 검증만 한다고 말하세요.
2. 세 단위를 언급하고 각각 본 숫자 집합이 필요하다고 말하세요.
3. 박스 인덱스 공식을 제시하고 예시 하나로 설명하세요.
4. 한 번의 순회와 조기 반환을 작성하세요.
5. 복잡도를 말하고 요청받으면 비트마스크 버전을 제안하세요.

저는 위 코드를 게시하기 전에 20,000개의 무작위 보드(일부는 유효하고 일부는 의도적으로 깨진)에 대해 단순한 행, 열, 박스 검사와 대조하여 테스트했습니다. 그런 간단한 무작위 검사는 연습할 때 좋은 습관입니다.

관련 연습

복잡도 용어는 Big O 치트 시트를, 다음에 무엇을 연습할지는 LeetCode Blind 75 목록을, 연습 방법은 코딩 면접 어시스턴트 가이드를 참고하세요.

코드를 작성하면서 접근법을 소리 내어 설명하세요. 녹취록을 보면 핵심 관찰을 코드 작성 전에 말했는지 알 수 있습니다. 실시간 평가에서는 AI 도구에 대한 회사 규칙을 따르세요.