C++ ] leetCode 36 - Valid Sudoku

 

 

 

리트코드 36 문제

 

 

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

 

총 9번 검사를 할건데 검사시 row, column, box에 대한 검사를 각각 수행한다.

 

검사는 길이가 9인 배열을 만들고 등장하는 숫자의 -1에 해당하는 인덱스 원소를 증가시켜 마지막에 검사했을 때 > 1인 경우 중복으로 등장했다고 판단한다.

 

row, column은 간단하고 box의 경우 아래 순서로 검사한다고 했을 때 처음 검사하게 되는 원소의 row 인덱스는 i / 3 * 3이고, col 인덱스는 i % 3 * 3 이다. 해당 row, col 부터 시작해 3x3 이중 루프로 인덱스를 증가하며 검사하면 된다.

 

0	1	2
3	4	5
6	7	8

 

 

 

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        bool ret = true;        
        for(int i = 0; i < 9; i++) {
            int row[9] = {0, };
            int col[9] = {0, };
            int box[9] = {0, };

            for(int j = 0; j < 9; j++) {
                if(board[i][j] != '.') {
                    row[board[i][j] - '1']++;
                }
                if(board[j][i] != '.') {
                    col[board[j][i] - '1']++;
                }
            }
            
            int boxRow = i / 3 * 3;
            int boxCol = i % 3 * 3;
            for(int l = boxRow; l < boxRow + 3; l++) {
                for(int m = boxCol; m < boxCol + 3; m++) {
                    if(board[l][m] != '.') {
                        box[board[l][m] - '1']++;
                    }
                }
            }
            
            for(int k = 0; k < 9; k++) {
                if(row[k] > 1 || col[k] > 1 || box[k] > 1) {
                    ret = false;
                    break;
                }
            }
        }

        return ret;
    }
};