LeetCode 36(Valid Sudoku, Python)

1. 문제 링크

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

Valid Sudoku - LeetCode

2. 문제 설명

• 스도쿠 문제가 주어졌을 때 valid 한 지 따져서 True, False 반환
• valid 하다는 것은 각 가로줄에 중복된 수가 없어야 함. 각 세로줄이나 각 3*3 박스도 마찬가지.
• input은 아래처럼 각 가로줄 리스트를 포함한 이중 리스트로 주어짐. 빈칸은 "."로 표시.
• [["5","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] ,[".","9","8",".",".",".",".","6","."] ,["8",".",".",".","6",".",".",".","3"] ,["4",".",".","8",".","3",".",".","1"] ,["7",".",".",".","2",".",".",".","6"] ,[".","6",".",".",".",".","2","8","."] ,[".",".",".","4","1","9",".",".","5"] ,[".",".",".",".","8",".",".","7","9"]]
• 이때 이 스도쿠가 실제로 풀려서 답이 존재하는지(solvable)는 따지지 않아도 됨.

3. 처음 풀이

• 각 가로줄이 valid 한지 체크하는 함수 check를 만든다.
• 리스트 컴프리헨션으로 주어진 가로줄에서 빈칸(".")이 아닌 것을 모아 리스트 temp로 만든다.
• temp 에 중복이 있다면 set으로 바꾸었을 때 개수가 줄어들기 때문에 len(set(temp)) == len(temp)를 통해 중복이 없는 지 체크 가능
• 이를 이용하여 각 가로줄에 대한 for문으로 각 가로줄의 valid를 체크.
• 세로줄을 체크하려면 가로줄에 정보에서 원하는 값을 가져와야함.
• i번째 세로줄을 체크하기 위해 i(0~8)에 대한 for문을 돌리고, 각 row에 대해 row[i]를 temp에 append한다. 그러면 temp가 i번째 새로줄이 된다. 이 temp에 대해 위에서 정의한 check함수로 valid를 확인한다.
• 박스는 조금 더 복잡하다. 결국 박스는 가로 3개 세로 3개니까 i, j 모두 range(3)에 대해 for문을 돌리고
• 3j번째 row의 3i부터 3*i+2번째까지 값
• 3j+1번째 row의 3i부터 3*i+2번째까지 값
• 3j+2번째 row의 3i부터 3*i+2번째까지 값을 모두 temp에 append하면 이것이 (j, i)에 해당하는 박스이다. 이 박스의 valide check하면 됨.

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        def check(row):
            temp = [x for x in row if x != '.']
            if len(temp) == len(set(temp)):
                return True
            else:
                return False
        
        for row in board:
            if check(row) == False:
                return False

        for i in range(9):
            temp = []
            for row in board:
                temp.append(row[i])
            if check(temp) == False:
                return False
        
        for i in range(3):
            for j in range(3):
                temp = []
                temp += board[3*j][3*i:3*i+3]
                temp += board[3*j+1][3*i:3*i+3]
                temp += board[3*j+2][3*i:3*i+3]
                if check(temp) == False:
                    return False
        
        return True

4. 다른 풀이

• 다른 풀이1
• 이 경우는 각 가로줄, 세로줄, 박스 중심으로 보지 않고 보드의 9*9가지 원소 중심으로 보며
• 이 원소가 속한 3개의 그룹(가로, 세로, 박스)에 할당해주며, 이미 할당 된 값이 있다면 False를 반환
• 예시) 2행 1열에 있는 5를 rows[2] 에 넣어 주었는데 이후 2행 3열에 또 5가 있다면 이를 rows[2]에 이미 있으므로 False
• 이때 각 박스의 번호를 k = (i//3)*3+j//3으로 하여 0번부터 9번까지 중복없이 할당되도록 하였음.

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

---

• 다른 풀이2
• 위 풀이에서 rows, cols, mMat을 따로 체크한 것을 하나의 리스트에 넣어 한 번에 체크함.
• i행 j열에 들어간 element(str)에 대해서
• 가로: (i, element), 세로: (element, j), 박스: (i//3, j//3, element)와 같은 튜플을 만들어서
• 리스트에 누적하여 추가함.
• 이때 리스트의 튜플들 중 중복되는 쌍이 하나라도 있다면 그것은 무조건 같은 그룹(가로/세로/박스)에서 중복될 수 밖에 없는데 그 이유는 i, j는 int이고 element는 str이기 때문에 (i, elemnet) == (element, j)일 수는 없음. 따라서 중복이 생겼다면 같은 그룹(가로/세로/박스)에서 같은 튜플이 있다는 것이고 그렇다면 valid하지 않다.

class Solution(object):
    def isValidSudoku(self, board):
        res = []
        for i in range(9):
            for j in range(9):
                element = board[i][j]
                if element != '.':
                    res += [(i, element), (element, j), (i // 3, j // 3, element)]
        return len(res) == len(set(res))

5. 배운 점

• 다른 풀이2에서 type 을 이용하는 아이디어가 재미있었다.
• 하지만 가독성을 생각하면 다른 풀이1이 좋았다.