2021-01-11] Valid Sudoku

 

오늘의 문제:

leetcode.com/problems/valid-sudoku/

Valid Sudoku - LeetCode

 

sudoku에 대해서 이해하고 있다면, 문제는 쉬울 것이다, 총 9X9 행렬이 주어지고, sudoku로써 맞는지 검증하는 문제이다.

예시의 그림을 보며 이해해 보자.

<예시 1번>

 

sudoku의 조건은 결국 아래 2가지로 정리될 것 같다.

1)  각 n행,n열 각각 모든 숫자들이 1-9 까지 중복되지 않고 들어간다.

2) 각 subbox ( 3X3 ) 또한 모든 숫자들이 1-9까지 중복되지 않고 들어간다.

 

1,2  모두 and 조건으로 만족해야지만 sudoku 행렬로 가능하다. 코드를 보며 좀 더 보도록 한다.

 

문제풀이)

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        sudokuint=[1,2,3,4,5,6,7,8,9] # 1-9 까지의 sudoku 숫자 ( 불변 list, 복사용 )
        checkedrow=list(sudokuint) # 각 row에 대해 1-9를 체크할 list (가변 list) 
        checkedcol=list(sudokuint) # 각 col에 대해 1-9를 체크할 list (가변 list)
        checkedsubbox=list(sudokuint) # 각 subbox(3X3)에 대해 1-9를 체크할 list (가변 list)
        for row in range(len(board)):
            rowdotcnt=0 # 입력값의 '.' 으로 값이 없는 애들을 count할 변수
            coldotcnt=0
            for col in range(len(board[row])):
                sbdotcnt=0
                if row%3==0 and col%3==0: # subbox의 시작점 (0,0 / 0,3 / 3,0 / 3,3 등...)
                    for i in range(3):
                        for j in range(3):
                            subboxval=board[col+j][row+i] # ( subbox의 값 검증 )
                            if subboxval=='.':
                                sbdotcnt=sbdotcnt+1
                            if subboxval!='.' and int(subboxval) in sudokuint:
                                if int(subboxval) not in checkedsubbox: 
                                    # 찾는 값이 없으면 0으로 변했는데 중복되어 찾는다고 판단
                                    return False # 중복되는 값이 있으면 sudoku는 성립하지 않는다.
                                checkedsubbox[checkedsubbox.index(int(subboxval))]=0 
                                # 찾는 값이 중복되지 않으면 0으로 치환
                    #print('checkedsubbox = {}'.format(checkedsubbox))
                    if len(sudokuint)-sbdotcnt != checkedsubbox.count(0): 
                    # 한번더 검증 ( 1-9이므로 9개에서 dot의 개수를 뺀 것과 0으로 만들어진 것의 개수가 다르면 중복된 값이 있다고 판단 
                        #print('subbox error')
                        return False
                    checkedsubbox=list(sudokuint) # 다음 번 검증을 위해 초기화
                colval=board[col][row]
                rowval=board[row][col]
                if rowval=='.':
                    rowdotcnt=rowdotcnt+1
                elif int(rowval) in sudokuint:
                    if int(rowval) not in checkedrow:
                        return False
                    checkedrow[checkedrow.index(int(rowval))]=0
                #print(rowval,colval)
                if colval=='.':
                    coldotcnt=coldotcnt+1
                elif int(colval) in sudokuint:
                    if int(colval) not in checkedcol:
                        return False
                    checkedcol[checkedcol.index(int(colval))]=0
            #print('checkedrow = {}'.format(checkedrow))
            #print('checkedcol = {}'.format(checkedcol))
            #print('checkedrow = {}'.format(checkedrow))
            #print('sudokuint = {} , rowdotcnt={}, checkedrow.count={}'.format(len(sudokuint),rowdotcnt,checkedrow.count(0)))
            if len(sudokuint)-rowdotcnt != checkedrow.count(0):
                #print('row error')
                return False
            if len(sudokuint)-coldotcnt != checkedcol.count(0):
                #print('col error')
                return False
            checkedrow=list(sudokuint)
            checkedcol=list(sudokuint)   
        return True
                
        

 

 

 

<문제 풀이의 성능>

 

너무 오래걸려서 구린것을 알 수 있다.. 좀더 좋은 방법이 있으려나..
슬슬 어려운 문제들이 나오며.. Daily에 나오는 문제는 못풀고 다른문제를 풀고있는 자신이 조금은 안타깝지만..

하루 한문제라는 것의 큰 목표를 이루기위한 내용이니 스스로에게 위안을 주자ㅋㅋ 힘내라 겜충이..