[lettCode/JS] 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:

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. 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.

스도쿠가 있는데, rules에서 정한 조건으로만 틀렸는지 잘 풀고있는지 체크하는 로직이다.
board[row][0] -> 1~9 까지 중복이 없는지
board[0][col] -> 1~9 까지 중복이 없는지
3x3 칸에 1~9까지 중복이 없는지
3개의 조건으로 체크를 한다.

스도쿠 특성상 이렇게 체크하면 풀 수 없는 "false" 인 경우도 나온다.

입출력 예

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 the 5 in the top left corner being modified to 8. 
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 '.'.

 

 

---

내 솔루션

• row 1줄 씩 체크, col 1줄 씩 체크 로직에 3x3 칸마다 따로 nine 이라는 Array에 추가하여 검사하는 방식으로 풀었다.
• 스도쿠 보드의 순회가 많은 것보다 isUnique() 가 반복이 1번더 있기 때문에 느렸던 것으로 추측하고 있다.
• 해결법은 isUnique()를 최적화 하거나 cols, rows, nine을 Set() 으로 초기화해서 has() 함수를 써서 push() 전에 체크하여 false를 return 해버리면 조금 더 빨라질 것 같다.

var isValidSudoku = function(board) {
  const isUnique = (nums) => {
    const newNums = nums.filter(n => n !== '.')
    const unique = new Set(newNums);
    return newNums.length === unique.size;
  }
  const nine = Array.from(Array(9), e => Array());
  for(let row = 0; row < board.length; row++) {
    if(!isUnique(board[row])) return false;
    const cols = [];
    for(let col = 0; col < board[0].length; col++) {
      const idx = Math.floor(col / 3) + Math.floor(row / 3) * 3;
      cols.push(board[col][row])
      nine[idx].push(board[col][row])
      if(nine[idx].length === board.length && !isUnique(nine[idx])) return false;
    }
    if(!isUnique(cols)) return false;
  }  
  return true;
};

 

 

감상평

• 생각보다 오래 걸렸다. nested array Declare 하는 것이 헷갈려서 ㅋㅋ