리트코드 문제 36, 38

36. Valid Sudoku

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

입력: board = [[“8”,”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”]]

출력: False

풀이 1

class Solution:
    def isValidSudoku(self, board):
        return (self.is_row_valid(board) and self.is_col_valid(board) and self.is_square_valid(board))

    def is_row_valid(self, board):
        for row in board:
            if not self.is_unit_valid(row):
                return False
        return True

    def is_col_valid(self, board):
        for col in zip(*board):
            if not self.is_unit_valid(col):
                return False
        return True

    def is_square_valid(self, board):
        for i in (0, 3, 6):
            for j in (0, 3, 6):
                square = [board[x][y] for x in range(i, i + 3) for y in range(j, j + 3)]
                if not self.is_unit_valid(square):
                    return False
        return True

    def is_unit_valid(self, unit):
        unit = [i for i in unit if i != '.']
        return len(set(unit)) == len(unit)

• isValidSudoku는 스도쿠 보드의 모든 숫자를 행, 열, 3x3 정사각형 단위로 확인하며 유효한 스도쿠 보드인지 확인하는 함수이다.
• is_row_valid, is_col_valid, is_square_valid는 각각 행, 열, 3x3 정사각형에서 모든 숫자를 넘겨받으며 중복되는 숫자가 있는지 확인하는 함수이다.
• is_unit_valid는 중복되는 숫자가 있는지 확인하는 함수이다.

---

38. Count and Say

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

countAndSay(1) = “1” countAndSay(n) is the way you would “say” the digit string from countAndSay(n-1), which is then converted into a different digit string. To determine how you “say” a digit string, split it into the minimal number of substrings such that each substring contains exactly one unique digit. Then for each substring, say the number of digits, then say the digit. Finally, concatenate every said digit.

입력: n = 4

출력: “1211”

설명: \n countAndSay(1) = “1” \n countAndSay(2) = say “1” = one 1 = “11” \n countAndSay(3) = say “11” = two 1’s = “21” \n countAndSay(4) = say “21” = one 2 + one 1 = “12” + “11” = “1211”

내 풀이

class Solution:
    def countAndSay(self, n: int) -> str:
        self.iteration = 0
        self.n = n
        def countNum(num: str) -> str:
            self.iteration += 1
            if self.iteration == 1:
                return countNum(str(1))
            
            elif self.iteration <= self.n:            
                prev_i = num[0] 
                c = 1
                output = ''
                for i in num[1:]:
                    if i != prev_i:
                        output = output + str(c) + prev_i 
                        c = 1
                    else:
                        c += 1
                    prev_i = i

                output = output + str(c) + prev_i
                return countNum(output)
            
            else:
                return num
        
        return countNum(str(1))

• countNum은 countAndSay로 전달받은 인수 n에 따라서 재귀로 결과값을 낼 수 있게 만든 함수이다.
• iteration은 반복횟수로, n보다 클시 output을 리턴한다.
• 쓸데없이 복잡해 보이는 방법으로, 그리 좋은 방법은 아닌 것으로 보인다.

결과

Runtime: 73 ms, faster than 51.48% of Python3 online submissions for Count and Say. Memory Usage: 14 MB, less than 53.52% of Python3 online submissions for Count and Say.

풀이 1: 간단히 표현한 재귀구조

class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1:
            return "1"
        
        def sayNumber(n):
            n = str(n)
            say = ""
            curDigit = n[0]
            digCount = 1
            for dig in n[1:]:
                if dig == curDigit:
                    digCount += 1
                else:
                    say += str(digCount) + curDigit
                    curDigit = dig
                    digCount = 1
            say += str(digCount) + curDigit
            return say
        
        return sayNumber(self.countAndSay(n-1))

중요내용

• 내 풀이 방법과 전반적으로 비슷하나 마지막에 재귀구조를 호출하여 리턴하는 방법에서 차이를 보인다.
• n이 1이 될때까지 countAndSay를 실행하다가 1이 되면 1을 리턴하여 그때부터 SayNumber을 실행한다.
• 내 풀이 방법에서 사용한 iteration 변수와 조건문을 실행시킬 필요가 없으므로 시간복잡도와 메모리 차지량이 내 풀이 방법보다 현저히 개선되었다.