Valid Sudoku
9개의 문자열로 이루어진 목록인 board가 주어집니다. 각 문자열은 9개의 문자로 구성되며, 각 문자열은 한 행에 해당합니다. 각 문자는 1부터 9까지의 숫자이거나 빈 칸을 나타내는 .입니다. 같은 행, 같은 열 또는 같은 3 × 3 박스에 어떤 숫자도 두 번 나타나지 않으면 true를 반환하고, 그렇지 않으면 false를 반환하세요. 채워진 칸만 확인합니다. 보드가 풀 수 있는 상태일 필요는 없습니다.
함수
- boardstring-array
- 각 행마다 9개의 문자로 이루어진 문자열 9개. 숫자 1부터 9까지와 빈 셀을 나타내는 .
- 반환값boolean
- 행, 열 또는 3 × 3 상자에 숫자가 반복되지 않으면 true, 그렇지 않으면 false
제약 조건
board.length == 9이고board[i].length == 9board[i][j]는1부터9까지의 숫자이거나.입니다.- 보드를 완성하는 것이 불가능할 수도 있습니다. 채워진 셀 사이의 반복만 중요합니다.
예제
- 입력
- board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]
- 출력
- true
- 설명
- 각 행, 열, 박스에는 각 숫자가 최대 한 번씩만 들어갑니다. 0부터 세는 행 4인
.74..89.3에는 7, 4, 8, 9, 3이 각각 한 번씩 들어 있으며, 나머지 26개 그룹도 마찬가지이므로 답은true입니다.
- 입력
- board = ["3.64.....", "258..9..1", "...8.2...", "...9...43", ".6.1..28.", "....87.65", "8......24", "3.......6", "6....45.8"]
- 출력
- false
- 설명
- 0행과 7행은 모두
3으로 시작하므로, 0열에는 3이 두 개 있습니다. 두 셀은 서로 다른 행과 서로 다른 박스에 있으므로, 이 경우는 열 검사만으로 잡아낼 수 있습니다.
- 입력
- board = ["987..36.5", "2.6.8..13", ".1.64.75.", "8..261..4", "16.97.3.8", "..9.5..6.", "7.....49.", "..48.....", "5.1.....7"]
- 출력
- false
- 설명
- 0행 8열의
5와 2행 7열의5는 서로 다른 행과 서로 다른 열에 있지만, 둘 다 오른쪽 위 상자에 있으므로 답은false입니다.
제출 시 숨은 테스트 +16개
후속 질문
검사를 4 × 4 상자가 있고 기호 1부터 9와 A부터 G를 사용하는 16 × 16 보드에 맞게 일반화하세요. 코드에서 보드 크기에 따라 달라지는 숫자는 무엇이며, 상자 공식은 어떻게 바뀌나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
규칙에서 언급하는 그룹을 나열하세요. 그룹은 몇 개이며, 인덱싱하기 가장 어려운 종류는 무엇인가요?
행
r과 열c에 있는 셀은 정확히 하나의 상자에 속합니다. 정수 나눗셈을 사용하면r / 3은 셀이 어느 3행 묶음에 있는지,c / 3은 어느 3열 묶음에 있는지를 나타냅니다. 두 값을 결합해 0부터 8까지의 숫자 하나로 만듭니다.각 셀을 한 번씩 방문하세요. 각 (행, 숫자), (열, 숫자), (박스, 숫자) 쌍마다 방문 여부 플래그를 유지하세요. 세 그룹 중 어느 하나에서든 플래그가 이미 설정된 채워진 셀은 중복입니다.
풀이
각 숫자는 행, 열, 3 × 3 박스의 세 그룹에 동시에 속합니다. 행과 열은 인덱싱하기 쉽지만, 박스에서는 버그가 가장 많이 발생합니다. 박스에 0부터 8까지 번호를 매길 때는 (r / 3) * 3 + c / 3를 사용하면 되며, 81개 셀을 한 번 순회하면서 27개 그룹을 모두 확인할 수 있습니다.
각 행, 열, 박스를 각각 확인하세요
핵심 아이디어
규칙은 27개의 그룹을 정의합니다. 9개의 행, 9개의 열, 9개의 박스입니다. 각 그룹의 아홉 칸을 모아 점은 무시하고 그 안에서 숫자가 반복되는지 확인하세요. 반복되는 숫자가 있는 그룹이 없다면 보드는 유효합니다.
행 i는 board[i][0..8]이고 열 i는 board[0..8][i]입니다. 박스 i는 정수 나눗셈을 사용해 행 3 * (i / 3), 열 3 * (i % 3)에서 시작하므로 박스 5는 행 3, 열 6에서 시작합니다. 그 모서리에서 셀 k는 아래로 k / 3행, 오른쪽으로 k % 3열 떨어져 있습니다.
아홉 칸에서 반복되는 숫자를 찾으려면 숫자마다 확인 여부를 저장하고, 이미 표시된 숫자가 나오면 즉시 멈추세요. 81개의 셀을 각각 세 번씩, 즉 속한 각 그룹에서 한 번씩 읽으므로 총 243번 읽으며, 이는 고정된 작업량입니다. n × n 보드에서는 같은 방법의 비용이 O(n²)입니다.
알고리즘
i가 0부터 8까지일 때, 행i, 열i, 박스i를 각각 9개의 셀로 모읍니다.- 박스
i는top = 3 * (i / 3)및left = 3 * (i % 3)에서 시작합니다. 박스의 셀k는 행top + k / 3, 열left + k % 3에 있습니다. - 각 그룹에 대해 새로운 seen 플래그를 사용해 셀을 순회하고, 점은 건너뜁니다.
- 숫자에 이미 플래그가 지정되어 있다면
false를 반환합니다. - 27개 그룹을 모두 확인한 후
true를 반환합니다.
def has_repeat(cells):
seen = set()
for ch in cells:
if ch == '.':
continue
if ch in seen:
return True
seen.add(ch)
return False
def isValidSudoku(board):
for r in range(9):
if has_repeat(board[r][c] for c in range(9)):
return False
for c in range(9):
if has_repeat(board[r][c] for r in range(9)):
return False
for top in (0, 3, 6):
for left in (0, 3, 6):
box = (board[top + i][left + j] for i in range(3) for j in range(3))
if has_repeat(box):
return False
return True행, 열, 박스마다 확인한 항목을 기록하는 표를 사용해 한 번 순회하기
핵심 아이디어
그룹을 모으는 대신 각 셀을 한 번씩 방문해 세 가지 질문을 동시에 확인합니다. 9 × 9 플래그 테이블 세 개를 사용합니다. seenRow[r][d]는 숫자 d+1이 이미 행 r에 있다는 뜻이고, seenCol과 seenBox도 열과 박스에 대해 같은 방식으로 동작합니다.
셀 (r, c)은 박스 (r / 3) * 3 + c / 3에 속합니다. 첫 번째 부분은 세 박스로 이루어진 밴드를 선택합니다(행 0~2는 밴드 0, 행 3~5는 밴드 1, 행 6~8은 밴드 2). c / 3은 밴드 안의 박스를 선택합니다. 셀 (4, 7)은 박스 1 * 3 + 2 = 5, 즉 가운데 오른쪽 박스에 속합니다.
숫자가 채워진 각 셀에 대해 세 플래그 중 하나라도 이미 설정되어 있으면 해당 그룹에서 숫자가 반복된 것이므로 즉시 false를 반환합니다. 그렇지 않으면 세 플래그를 모두 설정합니다. 각 셀은 한 번씩 읽고 테이블에는 243개의 플래그가 있으므로, 9 × 9 보드에서는 시간과 메모리 사용량이 고정되며 n × n 보드에서는 O(n²)입니다.
알고리즘
seenRow,seenCol,seenBox를 만들고, 각각 9 × 9 크기로 초기값을 모두 false로 설정합니다.- 모든 셀
(r, c)을 방문하고, 점이 들어 있으면 건너뜁니다. d를 숫자에서 1을 뺀 값으로 두고,b = (r / 3) * 3 + c / 3으로 둡니다.seenRow[r][d],seenCol[c][d]또는seenBox[b][d]가 true이면false를 반환합니다.- 그렇지 않으면 세 항목을 모두 true로 설정합니다. 마지막 셀을 처리한 후
true를 반환합니다.
def isValidSudoku(board):
# seen_row[r][d] is True once digit d + 1 appears in row r; same for columns and boxes.
seen_row = [[False] * 9 for _ in range(9)]
seen_col = [[False] * 9 for _ in range(9)]
seen_box = [[False] * 9 for _ in range(9)]
for r in range(9):
for c in range(9):
ch = board[r][c]
if ch == '.':
continue
d = int(ch) - 1
b = (r // 3) * 3 + c // 3
if seen_row[r][d] or seen_col[c][d] or seen_box[b][d]:
return False
seen_row[r][d] = seen_col[c][d] = seen_box[b][d] = True
return True
함정과 경계 사례
행과 열 검사는 거의 틀리지 않습니다. 버그는 박스 인덱스와 무엇을 중복으로 간주하는지에 있습니다.
- 박스를
r / 3 + c / 3으로 계산하는 경우입니다. 이렇게 하면 0부터 4까지만 나오므로, 서로 다른 박스에 있는 셀(0, 3)과(3, 0)이 같은 번호를 공유하게 되고, 그곳에 있는 두 개의 7이 중복으로 보고됩니다.(r / 3) * 3 + c / 3을 사용하세요. 4 / 3이 박스 번호인1.33을 반환하는 JavaScript, Python 3 또는 Lua에서/로 나누는 경우입니다.Math.floor,//또는math.floor를 사용하세요..을 값으로 취급하는 경우입니다. 빈 보드의 각 행에는 점이 9개 있으며, 이는 유효합니다.- 퍼즐을 풀려고 하는 경우입니다. 행 0이
12345678.이고 아래쪽의 열 8에 9가 있다면, 행 0의 마지막 칸은 절대 채울 수 없습니다. 하지만 어떤 그룹에서도 숫자가 반복되지 않으므로 답은true입니다. - 행과 열은 검사하지만 박스는 검사하지 않는 경우입니다. 각 행이 이전 행을 한 칸씩 왼쪽으로 이동한 완성된 격자에는 어떤 행이나 열에도 중복이 없지만, 모든 박스에는 중복이 있습니다.
자주 묻는 질문4
Valid Sudoku의 시간 복잡도는 얼마인가요?
보드에는 항상 81개의 셀이 있으므로 두 접근 방식 모두 O(1) 시간에 실행되고 O(1) 메모리를 사용합니다. 일반적인 n × n 스도쿠에서는 한 번 순회하는 검사 방식이 n²개의 각 셀을 한 번씩 읽고 3n²개의 플래그를 유지하므로 시간과 메모리 모두 O(n²)입니다.
유효한 스도쿠 보드는 반드시 풀 수 있어야 하나요?
아니요. 여기서 유효하다는 것은 이미 채워진 셀들 사이에서 같은 숫자가 행, 열 또는 3 × 3 상자에 반복되지 않는다는 뜻일 뿐입니다. 보드는 이 검사를 통과하고도 해답이 없을 수 있습니다. 풀 수 있는지 판단하려면 백트래킹과 같은 탐색이 필요하며, 이는 별개의 문제입니다.
셀은 어느 3 × 3 상자에 있는지 어떻게 찾나요?
정수 나눗셈에서 r / 3은 행의 띠(0, 1 또는 2)를 나타내고, c / 3은 열의 묶음을 나타냅니다. (r / 3) * 3 + c / 3은 상자에 왼쪽에서 오른쪽으로, 위에서 아래로 0부터 8까지 번호를 매깁니다. 셀 (7, 1)은 왼쪽 아래 상자인 2 * 3 + 0 = 6번 상자에 있습니다.
비트 마스크로 유효한 스도쿠를 풀 수 있을까요?
네. 각 행, 열, 박스에 정수 하나씩 할당하고, 비트 d는 숫자 d+1을 확인했음을 의미하게 하세요. 채워진 셀에 대해서는 1 << d를 계산하세요. 이 값이 세 마스크 중 어느 하나와 AND 연산했을 때 0이 아니면 숫자가 반복된 것이고, 그렇지 않으면 세 마스크 모두에 OR 연산으로 추가하세요. 이렇게 하면 243개의 플래그 대신 정수 27개를 사용하면서도 동일한 단일 순회 로직을 유지할 수 있습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def isValidSudoku(board):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]
기대값
true