[LeetCode/Kotlin]Medium - 36. Valid Sudoku

Valid Sudoku - LeetCode

문제

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

 

풀이

나의 풀이법

풀이 접근 과정

그냥 각 줄마다 가지고 있는 숫자를 체크하는 방식으로 풀면 되겠다고 생각했다.

그렇게 풀었더니 바로 해결되었다.

최종 소스코드

class Solution {
    fun isValidSudoku(board: Array<CharArray>): Boolean {
        val rowArray = Array(9) { BooleanArray(10) { false } }
        val columnArray = Array(9) { BooleanArray(10) { false } }
        val blockArray = Array(9) { BooleanArray(10) { false } }

        board.forEachIndexed { i, chars -> 
            chars.forEachIndexed { j, c ->
                if (c != '.') {
                    val num = c - '0'

                    if (rowArray[i][num]) return false
                    else rowArray[i][num] = true

                    if (columnArray[j][num]) return false
                    else columnArray[j][num] = true

                    val blockIndex: Int = ((i/3)*3) + (j/3)
                    if (blockArray[blockIndex][num]) return false
                    else blockArray[blockIndex][num] = true
                }
            }
        }

        return true
    }
}

• 각 열에서 가지고 있는 숫자를 체크할 이중 배열 rowArray
• 각 행에서 가지고 있는 숫자를 체크할 이중 배열 columnArray
• 각 3*3 블럭에서 가지고 있는 숫자를 체크할 이중 배열 blockArray

위와 같이 세 개의 이중 배열을 선언한다.

board를 돌면서 현재 숫자를 각 배열 중 하나라고 가지고 있는 경우 바로 false를 리턴시켜버리며 종료한다.

block의 위치를 계산하는 방법은 아래와 같다.

열의 위치를 구하기 위하여 i를 3으로 나눈 몫에 다시 3을 곱한다.

그 값에 j를 3으로 나눈 몫을 더해주면 된다.

만약 내 위치가 (5,1) 위치라면 5에서 3으로 나눈 몫 1에서 3을 곱해주고 거기에 1에서 3을 나눈 몫 0을 더해주면 3이 blockIndex가 된다.

위와 같이 계산을 해주면 blockIndex는 아래 표와 같다.

0	1	2
3	4	5
6	7	8

최종적으로 return 된 값이 없이 for문이 끝나면 스도쿠를 만족하므로 true를 리턴한다.

 

 

---

Comment

blockIndex를 구하는 데만 살짝 20분 정도 소요되었고 나머지는 금방 해결했다.

복잡할 것이라 생각했는데 의외로 간단하게 해결되었다.

9*9에 제한적인 문제라 그런 것 같다.