LeetCode 36

Valid Sudoku

문제 출처

문제

Determine if a 9x9 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 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Example 1:

Input:
[
  ["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:
[
  ["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.
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.
The given board contain only digits 1-9 and the character '.'.
The given board size is always 9x9.

나의 코드

function isValidSudoku(board: string[][]): boolean {
  // 배열 요소들의 값 : boolean 형태로 저장
  interface RepeatFlag {
    [value: string]: boolean;
  }
  // 중첩 객체
  interface Memo {
    [index: number]: RepeatFlag;
  }

  let rowMemo: Memo = {};
  let columnMemo: Memo = {};
  let subBoxMemo: RepeatFlag = {}; // 9개 부분 박스 메모 Hash Map

  let i: number = 0; // 세로
  let j: number = 0; // 가로
  let jMax: number = 2; // 가로의 현재 최대값

  while (i < 9 && j < 9) {
    // cannot read ... of undefined Error 방지
    rowMemo[i] = rowMemo[i] ?? {}; // Null 병합 연산자 (Nullish coalescing operator)

    while (j <= jMax) {
      // cannot read ... of undefined Error 방지
      columnMemo[j] = columnMemo[j] ?? {};

      // 각 Hash Map 에 key 로 써줄 값 저장
      const currentValue: string = board[i][j];

      if (currentValue !== ".") {
        // 중복 감지 => return false
        if (
          rowMemo[i][currentValue] ||
          columnMemo[j][currentValue] ||
          subBoxMemo[currentValue]
        )
          return false;

        // 새 Memo
        rowMemo[i][currentValue] = true;
        columnMemo[j][currentValue] = true;
        subBoxMemo[currentValue] = true;
      }

      // 부분 Box 초기화
      if (j === jMax && (i + 1) % 3 === 0) subBoxMemo = {};

      j++;
    }
    i++;

    if (i === 9) {
      jMax += 3;
      i = 0;
    }

    j = jMax - 2;
  }

  return true;
}

참고 코드

  • javascript
var isValidSudoku = function (board) {
  for (let i = 0; i < 9; i++) {
    let row = new Set(),
      col = new Set(),
      box = new Set();

    for (let j = 0; j < 9; j++) {
      let _row = board[i][j];
      let _col = board[j][i];
      let _box =
        board[3 * Math.floor(i / 3) + Math.floor(j / 3)][3 * (i % 3) + (j % 3)];

      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;
};

배운점

  • Set.prototype.has()