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 '.'.
문제 풀이
일반 for문을 통해 row, col, box부분의 검사하는 로직을 작성 -> O(n^4)의 복잡도로 시간 초과 오류
내부에 row, col, box를 검사하는 for문 로직이 O(n^2)을 띄워 최종적으로 O(n^4)라는 시간 복자도를 가짐
개선
row, col, box에 유효성을 검증하기 위해 O(1)로 검사할 수 있도록 Set 자료구조를 이용하여 값을 관리
ex) rows[0] -> 0번째 row에 해당 하는 값들을 모아 두는 배열 -> rows[0].has(target)형태로 O(1)로 유효성 검사
없다면 새로 값 추가
있다면 중복으로 false리턴
중요한 건 box의 index를 구하는 것 2차원 배열을 1차원 index로 관리를 해야 함
boxIndex 구하는 법 : `Math.floor(y / 3) * 3 + Math.floor(x / 3);`
boxIndex = 0
boxIndex = 1
boxIndex = 2
boxIndex = 3
boxIndex = 4
boxIndex = 5
boxIndex = 6
boxIndex = 7
boxIndex = 8
/**
* @param {character[][]} board
* @return {boolean}
*/
var isValidSudoku = function(board) {
const rows = Array.from({length: 9}, () => new Set());
const cols = Array.from({length: 9}, () => new Set());
const boxs = Array.from({length: 9}, () => new Set());
let boxIndex = 0;
for (let y = 0; y < 9; y++) {
for (let x = 0; x < 9; x++) {
if (board[y][x] === '.') continue;
boxIndex = Math.floor(y / 3) * 3 + Math.floor(x / 3);
// row에 같은 값 체크
if (rows[y].has(board[y][x])) {
return false;
} else {
rows[y].add(board[y][x]);
}
// col에 같은 값 체크
if (cols[x].has(board[y][x])) {
return false;
} else {
cols[x].add(board[y][x]);
}
// 3x3 박스에 같은 값 체크
if (boxs[boxIndex].has(board[y][x])) {
return false;
} else {
boxs[boxIndex].add(board[y][x]);
}
}
}
return true;
};
결론
유효성 검증을 위해 판단하는 부분을 Set을 이용해 O(1)로 줄여 최종적으로 O(n^2)의 시간 복잡도로 문제를 해결해야 함.
boxs 배열을 1차원으로 관리하기 때문에 2차원 배열의 x, y값에 다른 적절한 위치를 계산하는 로직을 구해야 함.
