LeetCode 36 - Valid Sudoku (Medium)

문제

LeetCode - 36번

풀이 과정

스도쿠 를 구현하는 문제입니다.
대신 모든 로직을 구현하는 것은 아니고 채워진 숫자들에 대해서 스도쿠 조건을 만족하는지 판단하는 문제입니다.

먼저 3x3 크기의 서브 박스들에서 19 사이의 숫자들 중 중복이 존재하는지 검사합니다.
이후 각 행과 열을 순회하며 마찬가지로 19 사이의 숫자 중복성을 검사합니다.

코드

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function (board) {
  const isSubboxRepetition = checkSubboxes(board);
  if (!isSubboxRepetition) {
    return false;
  }

  for (let row = 0; row < 9; row += 1) {
    const cache = [];

    for (let col = 0; col < 9; col += 1) {
      if (board[row][col] === ".") {
        continue;
      }

      if (cache.includes(board[row][col])) {
        return false;
      }

      cache.push(board[row][col]);
    }
  }

  for (let col = 0; col < 9; col += 1) {
    const cache = [];

    for (let row = 0; row < 9; row += 1) {
      if (board[row][col] === ".") {
        continue;
      }

      if (cache.includes(board[row][col])) {
        return false;
      }

      cache.push(board[row][col]);
    }
  }

  return true;
};

function checkSubboxes(board) {
  const hashTable = new Map();

  for (let row = 0; row < 9; row += 1) {
    for (let col = 0; col < 9; col += 1) {
      if (board[row][col] !== ".") {
        const code = encode(row, col);

        if (hashTable.has(code)) {
          const digits = hashTable.get(code);
          if (digits.includes(board[row][col])) {
            return false;
          }

          digits.push(board[row][col]);
          hashTable.set(code, digits);
        } else {
          hashTable.set(code, [board[row][col]]);
        }
      }
    }
  }

  return true;
}

function encode(row, col) {
  return `${~~(row / 3)}${~~(col / 3)}`;
}