[LeetCode] 36. Valid Sudoku

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

Valid Sudoku - LeetCode

조건1. 행중복X

조건2. 열중복X

조건3. 3X3 Group 에서 중복X

 

조건 1,2는 hash를 사용하여 쉽게해결가능하다.여기서 문제는 조건3이다. 3X3 Group의 중복체크를 어떻게 할 것인가? 이의 해결은 간단한 수학이다.0~8의 고정 스도쿠이며, 이를 3으로 나누면 몫은 0~2가 된다.따라서 키값을 (row//3,col//3) 으로 주고 value는 해당그룹에 속하는 숫자들을 넣어 유효성을 체크한다.나의 경우 //3 을 생각못했다...따흑...저런방법이...

---

SOLUTION CODE

# PYTHON

# Best풀이
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        cols = collections.defaultdict(set)
        rows = collections.defaultdict(set)
        squares = collections.defaultdict(set) # key = (r / 3 , r / 3)

        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    continue
                if (board[r][c] in rows[r] or
                board[r][c] in cols[c] or
                board[r][c] in squares[(r//3,c//3)]):
                    return False
                cols[c].add(board[r][c])
                rows[r].add(board[r][c])
                squares[(r//3,c//3)].add(board[r][c])
        return True

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        
        # row중복체크 ; 숫자만남기고 중복 체크(set이용)
        for i in range(9):
            row = list(filter(lambda x: x.isalnum(),board[i]))
            if len(row) != len(set(row)):
                return False

        # col중복체크 ; 전치후 숫자만남기고 중복 체크(set이용)
        board_t = list(zip(*board))

        for i in range(9):
            col = list(filter(lambda x: x.isalnum(),board_t[i]))
            if len(col) != len(set(col)):
                return False

        boxes = collections.defaultdict(set)
        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    continue
                if(board[r][c] in boxes[(r//3,c//3)]):
                    return False
                boxes[(r//3,c//3)].add(board[r][c])

        return True

# C++

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        unordered_set<char> cols[9];
        unordered_set<char> rows[9];
        unordered_set<char> boxes[3][3];
        
        for(int r=0;r<9;r++)
        {
            for(int c=0;c<9;c++)
            {
                if (board[r][c] == '.') continue;

                if (rows[r].count(board[r][c]) || cols[c].count(board[r][c])
                ||boxes[r/3][c/3].count(board[r][c])){
                    return false;
                }

                cols[c].insert(board[r][c]);
                rows[r].insert(board[r][c]);
                boxes[r/3][c/3].insert(board[r][c]);
            }

        }
        return true;
    }
};