[LeetCode] Valid Sudoku (Kotlin)

https://leetcode.com/problems/valid-sudoku

스도쿠 문제이다. 완전탐색으로 해결했지만, 흥미로운 풀이가 있어 공유하려고 한다.

우선 처음 내가 푼 풀이는 완전탐색을 해서 col, row, sub-box를 검사하는 것이다. 또한, 방문했던 col, row, sub-box는 체크를 해서 시간을 줄이려고 했다.

lateinit var visit: Array<BooleanArray>
lateinit var col: BooleanArray
lateinit var row: BooleanArray
val set: HashSet<Char> = hashSetOf()

fun isValidSudoku(board: Array<CharArray>): Boolean {
    visit = Array(3) { BooleanArray(3) }
    col = BooleanArray(9)
    row = BooleanArray(9)
    if (board[0][0] == '.') {
        println(" ")
    }
    for (i in 0..board.lastIndex) {
        for (j in 0..board.lastIndex) {
            if (board[i][j] == '.') continue
            if (!isValid(i, j, board)) {
                return false
            }
        }
    }

    return true
}

fun isValid(x: Int, y: Int, board: Array<CharArray>): Boolean {
    if (!(checkSubBox(x, y, board) && checkRow(x, board) && checkCol(y, board))) {
        return false
    }
    return true
}

fun checkSubBox(x: Int, y: Int, board: Array<CharArray>): Boolean {
    var startX = x / 3
    var startY = y / 3

    if (visit[startX][startY]) {
        return true
    }
    visit[startX][startY] = true
    set.clear()
    startX *= 3
    startY *= 3
    for (i in startX..startX + 2) {
        for (j in startY..startY + 2) {
            val value = board[i][j]
            if (value == '.') continue
            if (!set.add(value)) {
                return false
            }
        }
    }
    return true
}

fun checkCol(y: Int, board: Array<CharArray>): Boolean {
    if (col[y]) {
        return true
    }
    col[y] = true
    set.clear()
    for (b in board) {
        if (b[y] == '.') continue
        if (!set.add(b[y])) {
            return false
        }
    }

    return true
}

fun checkRow(x: Int, board: Array<CharArray>): Boolean {
    if (row[x]) {
        return true
    }
    row[x] = true
    set.clear()
    for (b in board[x]) {
        if (b == '.') continue
        if (!set.add(b)) {
            return false
        }
    }

    return true
}

해결은 했지만 코드가 많이 길었다.

풀이를 보고 정말 읽기 쉬운 해답을 보았다.

fun isValidSudoku(board: Array<CharArray>): Boolean {
    val set = hashSetOf<String>()

    for (i in 0..board.lastIndex) {
        for (j in 0..board.lastIndex) {
            val n = board[i][j]
            if (n == '.') continue
            if (!(set.add("col[$i]$n") 
               && set.add("row[$j]$n") 
               && set.add("sub[${i / 3}][${j / 3}]$n"))) {
                return false
            }
        }
    }

    return true
}

문자열과 Set을 사용했다. 성능은 많이 좋아지진 않았지만, 코드도 간단하고 읽기도 쉬웠다.

이런 생각을 어떻게 했는지 대단했다.