leetcode 36, Valid Sudoku

들어가는 말

주어진 이차원 베열에 스도쿠 게임이 가능한지 알아보는 문제다.
스도쿠가 가능하려면 가로와 세로, 그리고 3x3 박스에 숫자가 1부터 9까지 중복되지 않고 들어가야 한다.

가로의 경우 주어진 배열을 가지고 검사할 수 있지만, 세로는 따로 배열을 만들어서 검사를 했다. 그리고 가로와 세로를 모두 검사했다면 3x3 박스도 검사해서 해당 이차원 배열이 스도쿠가 가능한지 확인했다.

코드 설명

일단 가로와 세로를 검사한다. 이때 세로의 경우 따로 배열을 만들어서 검사한다. 둘 중에 하나라도 거짓이면 이는 스도쿠가 불가능한 것이므로 false를 반환한다. 아니면 다시 숫자를 하나 더해 탐색한다.

위의 이중반복문이 끝났다면 이제는 박스를 검사한다. 따로 이차원 배열을 만들 필요 없이 인덱스를 이용해서 검사한다. 그래서 만일 검사에서 거짓이 나오면 flase를 반환하고 아니면 true를 반환한다.

class Solution {
    public static boolean[] num;

    public boolean isValidSudoku(char[][] board) {
        num = new boolean[10];
        boolean flag = true;
        int idx = 0;

        for(int i=0; i<9; i++){

            if(check(board[i]) && check(make_row(board, i))){
                continue;
            }else{
                return false;
            }           
        }

        for(int i=0; i<9; i+=3){
            for(int j=0; j<9; j+=3){
                if(!squre_check(i, j, board)){
                    return false;
                }
            }
        }

        return true;
    }

    public char[] make_row(char[][] board, int i){
        char[] row = new char[9];

        for(int j=0; j<9; j++){
            row[j] = board[j][i];
        }

        return row;
    }

    public boolean squre_check(int i, int j, char[][] board){
        num = new boolean[10];

        for(int h=i; h<i+3; h++){
            for(int k=j; k<j+3; k++){
                if(board[h][k] != '.'){
                    int tmp = board[h][k]-'0';
                    if(num[tmp] == true){
                    return false;
                    }
                    num[tmp] = true;
                }               

            }
        }

        return true;
    }

    public boolean check(char[] arr){
        num = new boolean[10];

        for(int i=0; i<9; i++){
            if(arr[i] != '.'){
                int tmp = arr[i]-'0';
                if(num[tmp] == true){
                    return false;
                }
                num[tmp] = true;
            }
        }

        return true;
    }

}

여담

풀이를 보니 hashset을 사용해서 풀기도 했다.

class Solution {
    public boolean isValidSudoku(char[][] board) {
        HashSet<Character>[] rows = new HashSet[9];
        HashSet<Character>[] cols = new HashSet[9];
        HashSet<Character>[] boxes = new HashSet[9];

        for(int i=0; i<9; i++){
            rows[i] = new HashSet<Character>();
            cols[i] = new HashSet<Character>();
            boxes[i] = new HashSet<Character>();
        }

        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                char tmp = board[i][j];

                if(tmp == '.'){
                    continue;
                }

                if(rows[i].contains(tmp)){
                    return false;
                }
                rows[i].add(tmp);

                if(cols[j].contains(tmp)){
                    return false;
                }
                cols[j].add(tmp);

                int idx = (i/3)*3 + j/3;
                if(boxes[idx].contains(tmp)){
                    return false;
                }
                boxes[idx].add(tmp);
            }
        }
        return true;
    }
}