[LeetCode] 36. Valid Sudoku

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

Valid Sudoku - LeetCode

 

 

내 풀이 :

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        def checkRow(r) :
            dic = collections.defaultdict(int)
            for a in range(9) :
                if board[r][a] == '.' : continue
                dic[board[r][a]] += 1
                if dic[board[r][a]] >= 2 :
                    return 0
            return 1

        
        def checkCol(c):
            dic = collections.defaultdict(int)
            for a in range(9) :
                if board[a][c] == '.' : continue
                dic[board[a][c]] += 1
                if dic[board[a][c]] >= 2 :
                    return 0
            return 1
        
        def checkGrid(r, c) :
            dir =[[0,1,2],[3,4,5],[6,7,8]]
            r,c = r//3, c//3
            dic = {}
            for x in dir[r] :
                for y in dir[c] :
                    if board[x][y] == '.' : continue
                    if board[x][y] not in dic :
                        dic[board[x][y]] = 0
                        dic[board[x][y]] += 1
                    else :
                        return 0
            return 1

        
        for i in range(len(board)) :
            for j in range(len(board)) :
                if board[i][j] != '.' :
                    if not checkRow(i) or not checkCol(j) or not checkGrid(i,j) :
                        print(i,j)
                        return False
        return True

 

 

다른 사람 풀이 :

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        
        rows = [set() for i in range(9)]
        cols = [set() for i in range(9)]
        mMat = [set() for i in range(9)]
        
        for i in range(9):
            for j in range(9):
                cur = board[i][j]
                if cur != '.':
                    
                    k = (i // 3 ) * 3 + j // 3
                
                    if cur not in rows[i]: rows[i].add(cur)
                    else: return False
                    
                    if cur not in cols[j]: cols[j].add(cur)
                    else: return False
                
                    if cur not in mMat[k]: mMat[k].add(cur)
                    else: return False
        return True

 

나는 무지성으로 함수 구현을 해줬기 때문에 코드가 엄청 길다...... 하지만 set()으로 각 miniMatrix, row,  col을 관리해줌으로서 코드 가독성도 높히고 짧게 구현할 수 있었던 것..! 여기서 한 가지 짚고 넘어가야할 점이 있다면 k이다. miniMatrix를 위한 변수이다. 다시 말해서, 9 * 9 격자에서 각 miniMatrix를 3 * 3으로 나눠서 생각했을 때, i와 j 값에 따라 해당 좌표가 속하는 위치를 구할 수 있다.

k = (i // 3) * 3 + j // 3

ex) i = 4  j = 7

 

(4 // 3) * 3 + 7 // 3 = 1 * 3 + 2 = 3 + 2 = 5

 

아래와 같이 i,j좌표가 속한 miniMatrix의 위치를 알 수 있다.