Leet code 36 - Valid Sudoku

board가 주어지면, 그 board가 valid한지 판단하는 문제이다. 특정영역에 한정해서 순회하면 되기 떄문에 문제풀이에 있어 굳이 시간 복잡도에 대한 큰 고려는 하지 않아도 된다.

 

---

나의 풀이

 

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:

        # 먼저 한줄씩 찾는다. 중복되면 바로 invalid 해쉬 이용.
        check = {}

        # 가로 검사.
        for r in board:
            for c in range(9):
                if r[c] in check and r[c] != ".":
                    return False
                check[r[c]] = 0

            check = {}

        # 세로 검사.
        for c in range(9):
            check = {}
            for r in range(9):
                if board[r][c] in check and board[r][c] != ".":
                    return False
                check[board[r][c]] = 0

        
        #하위박스 검사.
        for i in range(3):
            for j in range(3):
                check = {}  # 각 서브 박스마다 새로운 check 딕셔너리를 초기화
                # 3x3 서브 박스 내부의 모든 셀을 순회
                for x in range(3):
                    for y in range(3):
                        value = board[3*i + x][3*j + y]
                        if value != '.' and value in check:
                            return False
                        check[value] = 0



        return True

 

가로 검사와 세로검사 하위박스 검사. 세가지 부분으로 나눠 처리했다.

 

---

지피티가 제안한 풀이.

 

세개의 독립적 순회가 아닌 한번의 통합된 순회로 한번에 모든 것을 판단한다.

 

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [{} for i in range(9)]
        columns = [{} for i in range(9)]
        boxes = [{} for i in range(9)]

        for i in range(9):
            for j in range(9):
                num = board[i][j]
                if num != '.':
                    box_index = (i // 3 ) * 3 + j // 3

                    rows[i][num] = rows[i].get(num, 0) + 1
                    columns[j][num] = columns[j].get(num, 0) + 1
                    boxes[box_index][num] = boxes[box_index].get(num, 0) + 1

                    if rows[i][num] > 1 or columns[j][num] > 1 or boxes[box_index][num] > 1:
                        return False         
        return True

9개의 빈 딕셔너리를 각각 rows, cloums, boxes 로 만든다.

 

모든 셀을 확인할 수 있도록 i,j로 포문 을 만든 뒤

num = board[i][j]로 현재 셀에 있는 숫자를 가져온다.

이후 각각의 딕셔너리에 넣어 판단.