Daily LeetCode Challenge - 36. Valid Sudoku

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

오늘 문제는 9 x 9 의 스도쿠 배열이 주어졌을 때, 그 스도쿠 배열이 올바른 스도쿠인지 아닌지를 판별하는 문제였다.

이 문제는 완전탐색 문제로 모든 요소를 한번씩 다 검사해야하며, 공간복잡도를 줄이는게 관건인 문제였다.

처음 내 풀이는

class Solution {
    fun isValidSudoku(board: Array<CharArray>): Boolean {
        
        for(i in 0 until board.size) {
            
            val numbersCol = mutableSetOf<Char>('1','2','3','4','5','6','7','8','9')
            val numbersRow = mutableSetOf<Char>('1','2','3','4','5','6','7','8','9')
            
            for(j in 0 until board.size) {
                
                if(board[i][j] != '.') {
                    if(numbersCol.contains(board[i][j])) numbersCol.remove(board[i][j])
                    else return false
                }
                if(board[j][i] != '.') {
                    if(numbersRow.contains(board[j][i])) numbersRow.remove(board[j][i])
                    else return false
                }
            }
        }
        
        for(x in 0 until board.size step 3) {
            for(y in 0 until board.size step 3) {
                
                val numbers = mutableSetOf<Char>('1','2','3','4','5','6','7','8','9')
                for(i in x until x + 3) {
                    for(j in y until y + 3) {
                        if(board[i][j] != '.') {
                            if(numbers.contains(board[i][j])) numbers.remove(board[i][j])
                            else return false
                        }
                    }
                }
                
            }
        }
        
        return true
    }
}

와 같이 Brutal Force 로 비효율적으로 푸는 방식이었다.
Discussion 을 참조하여 더 좋은 풀이를 배울 수 있었는데, 발상을 전환하여서 set 에서 빼주는것이 아닌 set 에 더해가면서 중복된 요소가 있다면 false 를 반환하는 것이었다.

class Solution {
    fun isValidSudoku(board: Array<CharArray>): Boolean {
        
        val seen: HashSet<Pair<Char, Int>> = hashSetOf()

        for (i in board.indices) {
            for (j in board[i].indices) {
                board[i][j].run { 
                    if (this != '.') {
                        if (!seen.add(Pair(board[i][j], -10 + i)) || 
                            !seen.add(Pair(board[i][j], -20 + j)) || 
                            !seen.add(Pair(board[i][j], i/3 * 10 + j/3))
                        ) return false
                    }
                }
            }
        }

        return true
    }
}

위와 같이 풀면 시간복잡도 O(m*n) 에 공간복잡도 O(n) 을 통해서 문제를 풀 수 있었다.