![5/24 수 [LeetCode #36] 유효한 스도쿠 TIL](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fb6gJJ0%2FbtshiHi6S2g%2FEMdYlNqekbeBqDSCTRYK51%2Fimg.png)
[LeetCode] 36. 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:
- Each row must contain the digits
1-9without repetition.
- Each column must contain the digits
1-9without repetition.
- Each of the nine
3 x 3sub-boxes of the grid must contain the digits1-9without repetition.
Note:
- A Sudoku board (partially filled) could be valid but is not necessarily solvable.
- Only the filled cells need to be validated according to the mentioned rules.
Example 1:
Input: board =
[["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"]]
Output: true
Example 2:
Input: board =
[["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"]]
Output: false
Explanation: Same as Example 1, except with the5 in the top left corner being modified to8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.
Constraints:
board.length == 9
board[i].length == 9
board[i][j]is a digit1-9or'.'.
나의 풀이:
// 행당, 열당, 3*3의 미니보드 당 각각 중복되는 1-9의 숫자가 있는지 검사하기
function isValidSudoku(board) {
// 1. 한 row 안의 1-9 빈도수 세기 및 중복 검사
// time: O(row * col) = O(N^2)
for (let row = 0; row < board.length; row++) { // O(row)
const rowDuplicateCount = new Map();
for (let num of board[row]) { // O(col)
if (num !== ".") {
if (rowDuplicateCount.has(num)) return false;
rowDuplicateCount.set(num, true);
}
}
}
// 2. 한 column의 1-9 빈도수 세기 및 중복 검사
// time: O(col * row) = O(N^2)
for (let column = 0; column < board[0].length; column++) { // O(col)
const columnDuplicateCount = new Map();
for (let row of board) { // O(row)
const num = row[column];
if (num !== ".") {
// console.log('current culumn: ', column, ' current number: ', num);
if (columnDuplicateCount.has(num)) return false;
columnDuplicateCount.set(num, true);
}
}
}
// 3. 한 subSquare 안의 1-9 빈도수 세기 및 중복 검사
// time: O(row/3) * { O(col/3) + 4O(3) } * O(9) => O(N) * { O(N) + O(1) } * O(1) => O(N^2)
for (let i = 0; i < 9; i += 3) { // O(row/3)
for (let j = 0; j < 9; j += 3) { // O(col/3)
const subSquareCount = new Map();
const subSquare = board.slice(i, i + 3).map((row) => row.slice(j, j + 3)).flat(); // O(3) + O(3) + O(3) + O(3) => O(1)
// console.log('i, j, first subSquare : ', i, j, subSquare);
for (let num of subSquare) { // O(9)
if (num !== ".") {
if (subSquareCount.has(num)) return false;
subSquareCount.set(num, true);
}
}
}
}
return true;
}- 행과 열을 도는 이중 루프를 3번 (각각 행, 렬, 3x3 검사를 위해) 사용했는데 이를 한 번의 루프 안으로 통합하는 작업을 하고 싶었다. 3x3에서 생각이 막혔는데 다른 사람의 풀이에서 바로 알 수 있었다.
다른 풀이:
// 위의 해법과 논리가 같다. 다만
// i, j 한번의 루프 안에서 행/렬/3*3을 전부 처리한 해법:
function hashSetSolution(board) {
for (let i = 0; i < 9; i++) {
let row = new Set(),
col = new Set(),
box = new Set();
/*
00 01 02 | 03 04 05 | 06 07 08
10 11 12 | 13 14 15 | 16 17 18 // i = 0, 1, 2
20 21 22 | 23 24 25 | 26 27 28
------------------------------
30 31 32 | 33 34 35 | 36 37 38
40 41 42 | 43 44 45 | 46 47 48 // i = 3, 4, 5
50 51 52 | 53 54 55 | 56 57 58
------------------------------
60 61 62 | 63 64 65 | 66 67 68
70 71 72 | 73 74 75 | 76 77 78 // i = 6, 7, 8
80 81 82 | 83 84 85 | 86 87 88
*/
for (let j = 0; j < 9; j++) {
let _row = board[i][j]; // [0][0->8]
let _col = board[j][i]; // [0->8][0]
let _box = board[3 * Math.floor(i / 3) + Math.floor(j / 3)][3 * (i % 3) + (j % 3)];
// i=0, j=0->2일 때, board[3 * 0 + 0][3 * 0 + 0->2] = board[0][0->2]
// i=0, j=3->5일 때, board[3 * 0 + 1][3 * 0 + 0->2] = board[1][0->2]
// i=0, j=6->8일 때, board[3 * 0 + 2][3 * 0 + 0->2] = board[2][0->2]
//
// i=1, j=0->2일 때, board[3 * 0 + 0][3 * 1 + 0->2] = board[0][3->5]
// i=1, j=3->5일 때, board[3 * 0 + 1][3 * 1 + 0->2] = board[1][3->5]
// i=1, j=6->8일 때, board[3 * 0 + 2][3 * 1 + 0->2] = board[2][3->5]
// ...
if (_row != '.') {
if (row.has(_row)) return false;
row.add(_row);
}
if (_col != '.') {
if (col.has(_col)) return false;
col.add(_col);
}
if (_box != '.') {
if (box.has(_box)) return false;
box.add(_box);
}
}
}
return true;
}
// 내가 하나의 루프로 통합하려고 했던 처음의 시도:
function isValidSudoku(board) {
// 0. 한 번의 루프로 통합
for (let row = 0; row < board.length; row++) {
const rowDuplicateCount = {};
const colDuplicateCount = {};
const subSquareDuplicateCount = {};
for (let col = 0; col < board[0].length; col++) {
const num = board[row][col];
if (num !== ".") {
if (num in rowDuplicateCount[row] || num in colDuplicateCount[row] || num in subSquareDuplicateCount[row]) {
return false;
}
// store row, col duplicate info
rowDuplicateCount[row] ? rowDuplicateCount[row][num] = true : rowDuplicateCount[row] = { num: true };
colDuplicateCount[col] ? colDuplicateCount[col][num] = true : colDuplicateCount[col] = { num: true };
// subsquare numbering:
// [0 - 3][0 - 3] => 0 / [0 - 3][3 - 6] => 1 / [0 - 3][6 - 9] => 2
// [3 - 6][0 - 3] => 3 / [3 - 6][3 - 6] => 4 / [3 - 6][6 - 9] => 5
// [6 - 9][0 - 3] => 6 / [6 - 9][3 - 6] => 7 / [6 - 9][6 - 9] => 8
// row: Math...
// []...
subSquareDuplicateCount[row] ? subSquareDuplicateCount[row][num] = true : subSquareDuplicateCount[row] = { num: true }; // 여기서 건너뜀
...
}
}
}
}
// Set을 하나만 쓰고 방금 시도하던 방식와 더 유사한 풀이:
function singleSetSolution(board) {
let set = new Set();
for(let r = 0; r < board.length; r++){
for(let c = 0; c < board[r].length; c++){
let val = board[r][c];
if(val === '.')
continue;
//basically, formula is 3 * row + col --> to turn 2d array into 1d array
//using Math.floor(row/3) + Math.floor(col/3) --> so we can find row and col of our sub box
let boxNum = 3 * Math.floor(r/3) + Math.floor(c/3);
let inRow = `row: ${r}, value: ${val}`;
let inCol = `col: ${c}, value: ${val}`;
let inSubBox = `subBox: ${boxNum}, value: ${val}`;
if(set.has(inRow) || set.has(inCol) || set.has(inSubBox))
return false;
set.add(inRow);
set.add(inCol);
set.add(inSubBox);
}
}
return true;
}
알게 된 점:
- 2D 배열 완전 정복: i로 바깥 루프를, j로 내부 루프를 돈다고 할 때
- 행별로 순회하기(= 바깥 루프가 한 번 돌 때 한 줄의 행을 검사하기) :
board[i][j]
- 열별로 순회하기(= 바깥 루프가 한 번 돌 때 한 줄의 열을 검사하기) :
board[j][i]
- (3 x 3)의 작은 정사각형별로 순환하기(= 바깥 루프가 한 번 돌 때 한 3 x 3 정사각형 순회하기) :
board[3 * Math.floor(i / 3) + Math.floor(j / 3)][3 * (i % 3) + (j % 3)]
- 행별로 순회하기(= 바깥 루프가 한 번 돌 때 한 줄의 행을 검사하기) :
- 2D 배열을 특정한 패턴으로 순회해야 할 일이 있을 때 아래와 같이 행렬 번호를 그려놓고 패턴을 찾으면 많은 도움이 된다.
00 01 02 | 03 04 05 | 06 07 08 10 11 12 | 13 14 15 | 16 17 18 // i = 0, 1, 2 20 21 22 | 23 24 25 | 26 27 28 ------------------------------ 30 31 32 | 33 34 35 | 36 37 38 40 41 42 | 43 44 45 | 46 47 48 // i = 3, 4, 5 50 51 52 | 53 54 55 | 56 57 58 ------------------------------ 60 61 62 | 63 64 65 | 66 67 68 70 71 72 | 73 74 75 | 76 77 78 // i = 6, 7, 8 80 81 82 | 83 84 85 | 86 87 88
※ 위 내용은 스스로 공부하며 적어둔 노트이며 불확실한 내용이 있을 수 있습니다. 학습용으로 적합하지 않음을 유념해주세요. ※
Uploaded by N2T