[LeetCode] 36. Valid Sudoku - 문제풀이

Description

주어진 9*9 스도쿠 문제가 유효한지 확인하는 문제입니다. 참고로 스도쿠는 각 행,렬,블록에 1-9의 숫자를 겹치지 않게 채워넣는 게임입니다.

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.

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 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 '.'.

Solution 1. HashSet 이용

public boolean isValidSudoku(char[][] board) {

    Set<String> set = new HashSet();

    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            char num = board[i][j];
            if (num != '.'){
                if (!set.add(num +"row:"+ i) ||
                    !set.add(num +"col:" +j) ||
                    !set.add(num + "block:" + i / 3 + "-" + j / 3)
                ) {
                    return false;
                }
            }
        }
    }
    return true;
}

중복을 저장할 경우 false를 반환하는 Set 자료구조를 이용하여 각각 행,렬,블록안의 숫자를 저장하고 겹치는케이스(add() > false반환)시 유효하지 않은 스도쿠므로 false를 반환해 줍니다.

Reference

Valid Sudoku - LeetCode