36. Valid Sudoku

🚥 문제 🚥

Top Interview 150 중
36. Valid Sudoku

🍿 난이도 : 리트코드 기준 Medium
🚧 알고리즘 : 행렬(matrix)

🚦 풀이1 🚦

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        def checkRow(row):
            checklist = []
            for i in range(9):
                if (row[i] != "." and row[i] in checklist):
                    return False
                checklist.append(row[i])
            return True
        def checkCol(board, col):
            checklist = []
            for i in range(9):
                if board[i][col] != "." and board[i][col] in checklist:
                    return False
                checklist.append(board[i][col])
            return True
		
        # row checking
        for i in range(9):
            if (checkRow(board[i]) == False):
                return False
                
        # column checking
        for j in range(9):
            if (checkCol(board, j) == False):
                return False
                
        # box checking
        for k in range(0,9,3):
            for m in range(0,9,3):
                if (checkRow(board[k][m:m+3] + board[k+1][m:m+3] + board[k+2][m:m+3]) == False):
                    return False
                    
        return True

🚧 python의 list 자료구조를 사용했다.

🚧 하나의 list를 체크할 때는 checkRow를 사용했고, column checking과정에서는 각각 하나의 원소씩 체크했다. checklist라는 새로운 list를 만들어서 원소를 삽입했고, 만약 삽입과정에서 중복이 발생했을 경우에는 바로 false를 리턴했다.

🚧 이중배열로 구성된 board가 valid한지 확인하기 위해서 row, column, box 형태 순서로 체크했고, 체크 과정에서 문제가 발생하지 않았다면 True를, 한번이라도 False가 발생했다면 즉시 False를 리턴했다.

풀이 결과

생각보다 메모리 사용량도 많았고, 런타임시간도 오래걸려서, 다른 사람들의 솔루션을 보고 바꿔봤다.

🚦 풀이2 🚦

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        def checkRow(row):
            if (len(set(row)) != len(row)):
                return False
            return True
        def checkCol(board, col):
            column = []
            for i in range(9):
                column.append(board[i][col])
            return checkRow([i for i in column if i != '.'])
		
        # row checking
        for row in board:
            if (checkRow([i for i in row if i != '.']) == False):
                return False
        
        # column checking
        for j in range(9):
            if (checkCol(board, j) == False):
                return False
                
        # box checking
        for k in range(0,9,3):
            for m in range(0,9,3):
                box = board[k][m:m+3] + board[k+1][m:m+3] + board[k+2][m:m+3]
                if (checkRow([i for i in box if i != '.']) == False):
                    return False
        return True

🚧 위의 풀이와 비슷하게 python의 list 자료구조를 사용했다. 이번에는 checklist라는 새로운 배열을 사용하지 않고 [i for i in column if i != '.']와 같은 list comprehension으로 함수를 호출했다.

🚧 중복값이 있는지 확인하는 과정에서도 if (len(set(row)) != len(row)): 와 같이 set을 사용한 뒤 두 값의 길이를 비교했다. set이 중복값을 삭제시키므로, 두 값의 길이가 같지 않으면 중복값이 있었다는 뜻이 된다.

풀이 결과

런타임 기준에서 약 15프로 개선되었지만 메모리 사용량에서는 25프로정도 감소했음을 볼 수 있다.
한번 더 다른 사람의 코드를 보고 개선했다.

🚦 풀이3 🚦

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        sudoku = []
        for i, row in enumerate(board):
             for j, num in enumerate(row):
                if num != '.':
                    sudoku += [(i, num), (num, j), (i // 3, j // 3, num)]
        # print(sudoku)
        return len(sudoku) == len(set(sudoku))

🚧 python의 list, tuple을 사용했다.

🚧 enumerate(board)같은 파이썬 내장함수 enumerate를 사용했다. enumerate() 함수는 인덱스와 원소로 이루어진 튜플(tuple)을 만든다. 문제에서 제시한 첫 번째 예제라고 했을 때 enumerate(board)의 첫 번째 결과는 (0, ['5', '3', '.', '.', '7', '.', '.', '.', '.'])가 될 것이다.

🚧 row, column, box일 때의 튜플을 각각 sudoku list에 저장한 뒤 set했을 때의 길이와 실제 길이를 비교해서 return했다.
box일때는 9칸을 1칸으로 보고 거대한 3*3 array라고 생각하고 첫번재 칸을 (0, 1)인덱스로 지정해서 튜플을 생성했다.

풀이 결과

일단 코드 길이가 어마어마하게 짧아졌다... 와우
결과적으로도 런타임 실행속도에서 많은 개선이 일어났다.