5/24 수 [LeetCode #36] 유효한 스도쿠 TIL

[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-9 without repetition.

Each column must contain the digits 1-9 without repetition.

Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without 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 digit 1-9 or '.'.

나의 풀이:

// 행당, 열당, 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

[LeetCode] 36. Valid Sudoku

티스토리툴바