[LeetCode] 36. Valid Sudoku

[Medium] 36. Valid Sudoku

https://leetcode.com/problems/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.

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.

문제 설명

스도쿠의 룰 3개를 통해 주어진 스도쿠 판이 valid한지 검증해야 한다.

나의 풀이

O(N^2) 주어진 값을 통해서만 검증하면 되기 때문에 row, col, sub-matrix을 위한 hashset을 만들고, 각 단계를 순회하며 hashset에 중복이 발생할 경우 false를 리턴한다.

이중 배열을 순회하기 때문에 최악의 경우 N^2가 소요된다. (이렇게 단순 순회도 N^2로 보는게 맞나??)

class Solution {
    public boolean isValidSudoku(char[][] board) {
        char[][] rows_valid = new char[9][9];
        char[][] cols_valid = new char[9][9];
        char[][] subs_valid = new char[9][9];

        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                rows_valid[i][j] = '.';
                cols_valid[i][j] = '.';
                subs_valid[i][j] = '.';
            }
        }

        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                // row
                char row_val = board[i][j];
                char col_val = board[j][i];
                char sub_val = board[(j/3) + (i/3)*3][(j%3) + (i%3)*3];

                if(row_val != '.'){
                    if(rows_valid[i][row_val-'0'-1] != '.') return  false;
                    else rows_valid[i][row_val-'0'-1] = 1;
                }
                if(col_val != '.'){
                    if(cols_valid[i][col_val-'0'-1] != '.') return false;
                    else cols_valid[i][col_val-'0'-1] = 1;
                }
                if(sub_val != '.'){
                    if(subs_valid[i][sub_val-'0'-1] != '.') return false;
                    else subs_valid[i][sub_val-'0'-1] = 1;
                }
            }
        }
        return true;
    }
}

베스트 풀이

베스트라기 보다는 신박한 풀이다. 시간복잡도는 동일해 보이나, 나의 코드보다 훨씬 간결하다. row, col, sub-matrix의 각 값을 하나의 string으로 encoding한다.

'4' in row 7 is encoded as "(4)7".
'4' in column 7 is encoded as "7(4)".
'4' in the top-right block is encoded as "0(4)2".

이후, hashset에 각 string이 들어가 있는지를 확인한다.

public boolean isValidSudoku(char[][] board) {
    Set seen = new HashSet();
    for (int i=0; i<9; ++i) {
        for (int j=0; j<9; ++j) {
            char number = board[i][j];
            if (number != '.')
                if (!seen.add(number + " in row " + i) ||
                    !seen.add(number + " in column " + j) ||
                    !seen.add(number + " in block " + i/3 + "-" + j/3))
                    return false;
        }
    }
    return true;
}