[leetcode] 36. Valid Sudoku 풀이, 해설 (python)

[leetcode] 49. Group Anagrams 풀이, 해설 (python)

문제 링크

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

Valid Sudoku - LeetCode

 

스도쿠가 유효한지 확인하는 문제이다. 

완전한 스도쿠의 규칙을 모두 체크하지는 않고, 가로, 세로, 3*3에 중복된 값이 있는지 아닌지만 체크하면 된다. 

 

1차 풀이

멋있게 풀고 싶었지만, 시간상 가로,세로,3*3을 각각 for문을 돌려서 확인하는 풀이로 접근했다. 

(아래 2차 풀이로 설명하겠지만, 이중 for문 하나로 모든 것을 해결할 수 있는 나이스한 풀이가 있다. )

 

가로와 세로는 비교적 단순하지만, 3*3을 체크하는 로직이 까다로웠는데, 

이 부분은 중간좌표를 기준으로 x -1,0,1 y -1,0,1을 해서 구하는 로직으로 했다. 

그 과정에서 4중 for문을 써버렸다 ;; 

 

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        
        # 가로줄 확인 
        for row in board : 
            checks = set()
            for w in row :
                if w != '.' and w in checks:
                    return False
                checks.add(w)
                
        # 세로줄 확인 
        for c in range(9) : 
            checks = set()
            for row in board:
                if row[c] != '.' and row[c] in checks:
                    return False
                checks.add(row[c])
        
                
        # 3 * 3 확인 : 중심 좌표 기준으로 확인 
        for x in range(1,8,3):
            for y in range(1,8,3) :
                checks = set() 
                for dx in range(-1,2):
                    for dy in range(-1,2):
                        if board[x + dx][y + dy] != '.' and  board[x + dx][y + dy] in checks:
                            return False
                        checks.add( board[x + dx][y + dy])
                
                
                
                
        
        return True

 

이후 바로 O(9*9), for문 하나로 풀 수 있는 풀이를 설명하겠다. 

 

 

2차 풀이 (해설 참고)

해당 풀이는 아래 유투브를 참고했다. 

https://www.youtube.com/watch?v=TjFXEUCMqI8

 

이 방식은 for문을 돌면서, 가로,세로,사각형을 모두 확인하면서 중복이 있는지 확인 및 값을 세팅해주는 부분이다. 

눈여겨봐야 하는 부분은 사각형 체크 같은 경우 아래 좌표에서 모두 동일한 키 값을 설정하기 위해서 (r // 3, c // 3)으로 설정한 부분이다. 

(0,0) (0,1) (0,2)

(1,0) (1,1) (1,2)

(2,0) (2,1) (2,2)

 

rows = defaultdict(set)
cols = defaultdict(set)
squares = defaultdict(set)
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

        rows[r].add(board[r][c])
        cols[c].add(board[r][c])
        squares[(r//3,c//3)].add(board[r][c])
        
        
                
        
        return True