[Algorithm] Leetcode_Vaild Sdoku

JAsmine_log·2024년 3월 17일
0

Problems

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
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 '.'.

Analysis && Solutions

이 문제는 주어진 예제 안에서만 해결하면 된다. 따로 '.'에 예상되는 숫자를 넣어볼 필요가 없다. 그래서, 생각보다 행&열(row&col)을 평가하는 것은 쉬운편이다. subsections은 행렬의 기준을 어떻게 증가 시킬 지 헷갈렸는데, 좀 고민하기도 하고 다른 블로그를 참고하여 해결하였다. 행과열의 기준은 +3씩 증가시켰다.

  • 한줄 가로, 세로, 서브섹션에서 3*3로 9에서 1~9가 한 번씩만 등장할 때만 스도쿠가 가능
  • input은 숫자나 string이 아닌 char 형태
  • board.lengh=9행, bord[i].lenth=9열
  • subsection(3*3)은 행렬이 3씩 증가하여 기준 행렬이 됨
    board[0][0], board[0][3], board[0][6],
    board[3][0], board[3][3], board[3][6],
    board[6][0], board[6][3], board[6][6]
  • 위의 기준에서 subsection(3*3)에서 스도쿠가 가능한지 평가함

Code

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

        boolean bool=true;
        int size=9;

        //rows
        for (int i=0; i<size; i++ ){
            int visit[]={0,0,0,0,0,0,0,0,0,0};
            for (int j=0;j<size;j++){
                if(board[i][j]!='.' && visit[Character.getNumericValue(board[i][j])]==0){
                    visit[Character.getNumericValue(board[i][j])]=1;
                }
                else if(board[i][j]!='.' && visit[Character.getNumericValue(board[i][j])]==1){
                    return false;
                }
            }

        }

        //cols
        for (int i=0; i<size; i++ ){
            int visit[]={0,0,0,0,0,0,0,0,0,0};
            for (int j=0;j<size;j++){
                if(board[j][i]!='.' && visit[Character.getNumericValue(board[j][i])]==0){
                    visit[Character.getNumericValue(board[j][i])]=1;
                }
                else if(board[j][i]!='.' && visit[Character.getNumericValue(board[j][i])]==1){
                    return false;
                }
            }
        }

        //subsections
        for (int r=0 ; r < size ; r+=3) {
            for(int c=0 ;c < size ; c+=3){
                int visit[]={0,0,0,0,0,0,0,0,0,0};
                for(int i = r; i < r+3; i++) {
                    for (int j=c; j< c+3;j++){
                        if(board[i][j]!='.' && visit[Character.getNumericValue(board[i][j])] == 0){
                            visit[Character.getNumericValue(board[i][j])]=1;
                        }
                        else if(board[i][j]!='.' && visit[Character.getNumericValue(board[i][j])]==1){
                            return false;
                        }
                    }
                }
            }
        }
        return bool;
    }
}

Improved Code

친구가 코드 리뷰를 해주었다. 코드가 훨씬 깔끔해지고 Profeshional 해진 느낌이라 뿌듯 ㅎㅎ 아래 코드를 참고하셔도 좋을거 같습니다.

public class Solution {

    private static final int SIZE = 9;
    
    public boolean isValidSudoku(char[][] board) {
        //rows
        for (int i = 0; i < SIZE; i++) {
            boolean[] visit = {false, false, false, false, false, false, false, false, false, false};

            for (int j = 0; j < SIZE; j++) {
                if (board[i][j] == '.') continue; 
                int rowIndex = Character.getNumericValue(board[i][j]);
                if (visit[rowIndex]) {
                    return false;
                } else {
                    visit[rowIndex] = true;
                }
            }
        }

        //cols
        for (int i = 0; i < SIZE; i++) {
            boolean[] visit = {false, false, false, false, false, false, false, false, false, false};

            for (int j = 0; j < SIZE; j++) {
                if(board[j][i]=='.') continue;

                int colIndex = Character.getNumericValue(board[j][i]);
                if (visit[colIndex]) {
                    return false;
                } else{
                    visit[colIndex] = true;
                }
            }
        }

        //sub-boxes
        for (int r = 0; r < SIZE; r += 3) {
            for (int c = 0; c < SIZE; c += 3) {
                boolean[] visit = {false, false, false, false, false, false, false, false, false, false};

                for (int i = r; i < r + 3; i++) {
                    for (int j = c; j < c + 3; j++) {
                        if(board[i][j]=='.') continue;

                        int subIndex = Character.getNumericValue(board[i][j]);
                        if (visit[subIndex]) {
                            return false;
                        } else {
                            visit[subIndex] = true;
                        }
                    }
                }
            }
        }
        return true;
    }
}

Tip

char 타입의 value를 int로 변환

Character.getNumericValue(value)

추가 case (in Java)

                {{'.', '.', '.', '.', '5', '.', '.', '1', '.'},
                {'.', '4', '.', '3', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '3', '.', '.', '1'},
                {'8', '.', '.', '.', '.', '.', '.', '2', '.'},
                {'.', '.', '2', '.', '7', '.', '.', '.', '.'},
                {'.', '1', '5', '.', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '2', '.', '.', '.'},
                {'.', '2', '.', '9', '.', '.', '.', '.', '.'},
                {'.', '.', '4', '.', '.', '.', '.', '.', '.'}};

Reference

[1] https://velog.io/@redgem92/LeetCodeJavaValid-Sudoku

profile
Everyday Research & Development

0개의 댓글