Leetcode - 36. Valid Sudoku

문제

9x9크기의 스도쿠 보드와 값이 주어진다. 주어진 값들이 아래 스도쿠 조건을 만족하는지 확인하라.

• (1) 각 row (2) 각 column (3) 각 box에 중복 숫자가 없을것.

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

해결 O(1)

해시테이블 3개(행, 열, 3x3박스)를 만들고 배열을 한번 순회하는것만으로 체크할 수 있다. 배열의 크기는 9x9 고정이기 때문에 시간복잡도는 O(1)이다.

bool isValidSudoku(char** board, int boardSize, int* boardColSize){
    int row[9][9] = {0};
    int col[9][9] = {0};
    int box[9][9] = {0};
    
    for (int i = 0; i < 9; i++) { /* row */
        for (int j = 0; j < 9; j++) { /* column */
            if (board[i][j] == '.')
                continue;
            /* update row hashtable */
            if (row[i][board[i][j] - '1']++) return false;
            /* update column hashtable */
            if (col[j][board[i][j] - '1']++) return false;
            
            /* update box hashtable */
            if (0 <= i && i <= 2) {
                if (0 <= j && j <= 2)
                    if (box[0][board[i][j] - '1']++) return false;
                if (3 <= j && j <= 5)
                    if (box[1][board[i][j] - '1']++) return false;
                if (6 <= j && j <= 8)
                    if (box[2][board[i][j] - '1']++) return false;
            } else if (3 <= i && i <= 5) {
                if (0 <= j && j <= 2)
                    if (box[3][board[i][j] - '1']++) return false;
                if (3 <= j && j <= 5)
                    if (box[4][board[i][j] - '1']++) return false;
                if (6 <= j && j <= 8)
                    if (box[5][board[i][j] - '1']++) return false;
            } else if (6 <= i && i <= 8) {
                if (0 <= j && j <= 2)
                    if (box[6][board[i][j] - '1']++) return false;
                if (3 <= j && j <= 5)
                    if (box[7][board[i][j] - '1']++) return false;
                if (6 <= j && j <= 8)
                    if (box[8][board[i][j] - '1']++) return false;
            }
        }
    }
    return true;
}

box업데이트 부분이 엄청 반복코드가 많은데 idx를 간단하게 계산할 수 있는 공식이 역시 있었다. (i / 3) * 3 + (j / 3) 로 각 box의 index를 계산할 수 있음. 코드가 아래와 같이 훨씬 간단해짐.

bool isValidSudoku(char** board, int boardSize, int* boardColSize){
    int row[9][9] = {0};
    int col[9][9] = {0};
    int box[9][9] = {0};
    
    for (int i = 0; i < 9; i++) { /* row */
        for (int j = 0; j < 9; j++) { /* column */
            if (board[i][j] == '.')
                continue;
            /* update row hashtable */
            if (row[i][board[i][j] - '1']++) return false;
            /* update column hashtable */
            if (col[j][board[i][j] - '1']++) return false;
            /* update box hashtable */
            int idx = (i / 3) * 3 + (j / 3);
            if (box[idx][board[i][j] - '1']++) return false;
        }
    }
    return true;
}