ISH AI Blog

알고리즘 문제풀이 정리 - Arrays & Hashing (4)

·임성혁
Algorithm

이전 게시글에서 이어서 작성되는 4부이다.

You are given a 9 x 9 Sudoku board board. A Sudoku board is valid if the following rules are followed:

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

Return true if the Sudoku board is valid, otherwise return false

Note: A board does not need to be full or be solvable to be valid.

Example 1:

img
img

Input: board = 
[["1","2",".",".","3",".",".",".","."],
 ["4",".",".","5",".",".",".",".","."],
 [".","9","8",".",".",".",".",".","3"],
 ["5",".",".",".","6",".",".",".","4"],
 [".",".",".","8",".","3",".",".","5"],
 ["7",".",".",".","2",".",".",".","6"],
 [".",".",".",".",".",".","2",".","."],
 [".",".",".","4","1","9",".",".","8"],
 [".",".",".",".","8",".",".","7","9"]]
 
Output: true

Example 2:

Input: board = 
[["1","2",".",".","3",".",".",".","."],
 ["4",".",".","5",".",".",".",".","."],
 [".","9","1",".",".",".",".",".","3"],
 ["5",".",".",".","6",".",".",".","4"],
 [".",".",".","8",".","3",".",".","5"],
 ["7",".",".",".","2",".",".",".","6"],
 [".",".",".",".",".",".","2",".","."],
 [".",".",".","4","1","9",".",".","8"],
 [".",".",".",".","8",".",".","7","9"]]
 
Output: false

Explanation: There are two 1's in the top-left 3x3 sub-box.

Constraints:

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit 1-9 or '.'.

주의 : 대충 실패했다는 내용이니 이부분은 코드 보지말고 넘기세요

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        arr = [[[True for _ in range(10)] for _ in range(9)] for _ in range(9)]
        intboard = [[0 for _ in range(9)] for _ in range(9)]
        for i, column in enumerate(board):
            for j, num in enumerate(column):
                if not num==".":
                    intnum=int(num)
                    for k in range(9):
                        # 세로가능성 차단
                        arr[k][j][intnum]=False
                        # 가로가능성 차단
                        arr[i][k][intnum]=False # num 에 해당하는 숫자는 (i,k)에 올 수 없음.
                    # 3*3 차단
                    if i<3:
                        if j<3:
                            for a in range(3):
                                for b in range(3):
                                    arr[a][b][intnum]=False
                        elif j>5:
                            for a in range(3):
                                for b in range(6,9):
                                    arr[a][b][intnum]=False
                        else:
                            for a in range(3):
                                for b in range(3,6):
                                    arr[a][b][intnum]=False
                    elif i>5:
                        if j<3:
                            for a in range(6,9):
                                for b in range(3):
                                    arr[a][b][intnum]=False
                        elif j>5:
                            for a in range(6,9):
                                for b in range(6,9):
                                    arr[a][b][intnum]=False
                        else:
                            for a in range(6,9):
                                for b in range(3,6):
                                    arr[a][b][intnum]=False
                    else:
                        if j<3:
                            for a in range(3,6):
                                for b in range(3):
                                    arr[a][b][intnum]=False
                        elif j>5:
                            for a in range(3,6):
                                for b in range(6,9):
                                    arr[a][b][intnum]=False
                        else:
                            for a in range(3,6):
                                for b in range(3,6):
                                    arr[a][b][intnum]=False
                    intboard[i][j]=intnum # 숫자가 배정되었음을 기록
 
        print(intboard)
        cnt=0
        while True:
            if cnt==81:
                break
            cnt=0
            for i in range(9):
                for j in range(9):
                    if not intboard[i][j]==0:
                        cnt+=1
                        continue
                    temp=0
                    for k in range(1,10):
                        if arr[i][j][k]==True:
                            temp=k
                            if not temp==0:
                                temp=-1
                                break
                    if temp==0:
                        return False
                    elif temp==-1:
                        continue
                    intboard[i][j]=temp # 숫자 k 기입
                    for k in range(9):
                        # 세로가능성 차단
                        arr[k][j][temp]=False
                        # 가로가능성 차단
                        arr[i][k][temp]=False # num 에 해당하는 숫자는 (i,k)에 올 수 없음.
                    # 3*3 차단
                    if i<3:
                        if j<3:
                            for a in range(3):
                                for b in range(3):
                                    arr[a][b][temp]=False
                        elif j>5:
                            for a in range(3):
                                for b in range(6,9):
                                    arr[a][b][temp]=False
                        else:
                            for a in range(3):
                                for b in range(3,6):
                                    arr[a][b][temp]=False
                    elif i>5:
                        if j<3:
                            for a in range(6,9):
                                for b in range(3):
                                    arr[a][b][temp]=False
                        elif j>5:
                            for a in range(6,9):
                                for b in range(6,9):
                                    arr[a][b][temp]=False
                        else:
                            for a in range(6,9):
                                for b in range(3,6):
                                    arr[a][b][temp]=False
                    else:
                        if j<3:
                            for a in range(3,6):
                                for b in range(3):
                                    arr[a][b][temp]=False
                        elif j>5:
                            for a in range(3,6):
                                for b in range(6,9):
                                    arr[a][b][temp]=False
                        else:
                            for a in range(3,6):
                                for b in range(3,6):
                                    arr[a][b][temp]=False
        return True

처음에는

  1. 기본 가로, 세로, 칸 점검
  2. 스도쿠 채우기?

로 가면 되지 않을까 생각했는데 다시 생각해보니 각 비어있는 칸에 대해서 올 수 없는 숫자를 소거하면서 접근하면 되는거였다.

라고 생각하고 arr[가로][세로][가능성 있는 숫자 9개] 를 bool로 놓고 풀었는데 시간초과가 떴다.

생각해보니 당연한 것이 위의 방법은 인간이 푸는 방식이고, 컴퓨터는 가능성을 소거하면서 기억할 필요가 없다..

거기에 에초에 같은 줄이나 칸에 같은 숫자가 제시되어 풀 수 없게되는 경우를 고려하지 못했다.

이런 저런 방식으로 접근하며 계속 문제를 풀어봤는데 계속 시간초과가 뜨거나 오류가 떴다.

몇일을 고민하면서 답답해했는데 그러다가 문제를 다시 봤다.

Note: A board does not need to be full or be solvable to be valid.

!!!!!!!!!!!!!!!!

나는 지금까지 스도쿠를 다 풀 수 있을 때 True를 반환하도록 했는데 그럴 필요가 없는거였다.

수학적으로 증명하는 법은 모르겠지만 아무튼 주어진 숫자들 사이에서만 충돌이 나지 않으면 되는 것...

코드를 막 쓰다가 문득 이 점을 뒤늦게 깨닫고 지우고 주석처리하고 제출하니 Accept 되었다. (코드는 한번 더 넘기시오)

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row=[[False for _ in range(9)] for _ in range(9)]
        column=[[False for _ in range(9)] for _ in range(9)]
        sub_box=[[[False for _ in range(9)] for _ in range(3)] for _ in range(3)]
        number_filled=[[False for _ in range(9)] for _ in range(9)]
        row_n=[0 for _ in range(9)]
        column_n=[0 for _ in range(9)]
        sub_box_n=[[0 for _ in range(3)] for _ in range(3)]
 
        # 주어진 조건을 순회하며 숫자 기록
        for i in range(0,9):
            for j in range(0,9):
                if board[i][j]=='.':
                    continue
                num=int(board[i][j])-1
                if row[i][num]:
                    return False
                row[i][num]=True
                row_n[i]+=1
                if column[j][num]:
                    return False
                column[j][num]=True
                column_n[j]+=1
                a=i//3
                b=j//3
                if sub_box[a][b][num]:
                    return False
                sub_box[a][b][num]=True
                sub_box_n[a][b]+=1
                number_filled[i][j]=True
        '''
        assume=[[[True for _ in range(9)] for _ in range(9)] for _ in range(9)]
        assume_n=[[0 for _ in range(9)] for _ in range(9)]
 
        # 행 열 칸 조건3개 통합하기
        for i in range(0,9):
            for j in range(0,9):
                a=i//3
                b=j//3
                for k in range(0,9):
                    if row[i][k]:
                        assume[i][j][k]=False
                    if column[j][k]:
                        assume[i][j][k]=False
                    if sub_box[a][b][k]:
                        assume[i][j][k]=False
                count=0
                for k in range(0,9):
                    if assume[i][j][k]: # 가능성 있는 숫자가 몇개인지 count
                        count+=1
                assume_n[i][j]=count
        for i in range(0,9):
            for j in range (0,9): # 좌표 (i,j)를 체크하겠다.
                if number_filled[i][j]: # 이미 숫자가 있는 칸이면 넘어감
                    continue
                if assume_n[i][j]==0:
                    return False
 
        # Note: A board does not need to be full or be solvable to be valid.
        '''
        return True

필요없는 요소 다 쳐낸 최종 코드

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row=[[False for _ in range(9)] for _ in range(9)]
        column=[[False for _ in range(9)] for _ in range(9)]
        sub_box=[[[False for _ in range(9)] for _ in range(3)] for _ in range(3)]
 
        # 주어진 조건을 순회하며 숫자 기록
        for i in range(0,9):
            for j in range(0,9):
                if board[i][j]=='.':
                    continue
                num=int(board[i][j])-1
                if row[i][num]:
                    return False
                row[i][num]=True
                if column[j][num]:
                    return False
                column[j][num]=True
                a=i//3
                b=j//3
                if sub_box[a][b][num]:
                    return False
                sub_box[a][b][num]=True
        return True

bool을 기록하는 9x9 이차원 배열 3개를 만들어 관리했다.

row 9*9 / column 9*9 / sub_box 3*3*9 (sub_box는 편의를 위해 9를 다시 3*3으로 나누었다)

각 행, 열, 하위박스에 어느 숫자가 기록되어있는지 기록하는 배열을 만들었다.

예를들어, row[0][1]은 1(0+1)번째 행의 어딘가에 2(1+1)가 기록되었음을 의미한다.

sub_box를 어떻게 기록할지 고민을 많이 했는데, 이부분은 이차원 배열이 아니라 삼차원 배열로 만듬으로써 해결했다.

각 좌표에 대해 숫자를 읽어들이고 그 좌표가 속하는 행, 열, 하위박스에 대한 배열에 숫자를 기록하기 전에 그 숫자가 이미 기록되어있는지를 확인한다.

만약 이미 기록되어있다면 중복이니 False를 반환하고, 모든 좌표에 대해 중복이 없으면 True를 반환한다.

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        for row in range(9):
            seen = set()
            for i in range(9):
                if board[row][i] == ".": 
                    continue
                if board[row][i] in seen:
                    return False
                seen.add(board[row][i])
        
        for col in range(9):
            seen = set()
            for i in range(9):
                if board[i][col] == ".":
                    continue
                if board[i][col] in seen:
                    return False
                seen.add(board[i][col])
            
        for square in range(9):
            seen = set()
            for i in range(3):
                for j in range(3):
                    row = (square//3) * 3 + i
                    col = (square % 3) * 3 + j
                    if board[row][col] == ".":
                        continue
                    if board[row][col] in seen:
                        return False
                    seen.add(board[row][col])
        return True

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        cols = defaultdict(set)
        rows = defaultdict(set)
        squares = defaultdict(set)  
 
        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    continue
                if ( board[r][c] in rows[r]
                    or board[r][c] in cols[c]
                    or board[r][c] in squares[(r // 3, c // 3)]):
                    return False
 
                cols[c].add(board[r][c])
                rows[r].add(board[r][c])
                squares[(r // 3, c // 3)].add(board[r][c])
 
        return True

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [0] * 9
        cols = [0] * 9
        squares = [0] * 9
 
        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    continue
                
                val = int(board[r][c]) - 1
                if (1 << val) & rows[r]:
                    return False
                if (1 << val) & cols[c]:
                    return False
                if (1 << val) & squares[(r // 3) * 3 + (c // 3)]:
                    return False
                    
                rows[r] |= (1 << val)
                cols[c] |= (1 << val)
                squares[(r // 3) * 3 + (c // 3)] |= (1 << val)
 
        return True

Given an array of integers nums, return the length of the longest consecutive sequence of elements that can be formed.

A consecutive sequence is a sequence of elements in which each element is exactly 1 greater than the previous element. The elements do not have to be consecutive in the original array.

You must write an algorithm that runs in O(n) time.

Example 1:

Input: nums = [2,20,4,10,3,4,5]
 
Output: 4

Explanation: The longest consecutive sequence is [2, 3, 4, 5].

Example 2:

Input: nums = [0,3,2,5,4,6,1,1]
 
Output: 7

Constraints:

  • 0 <= nums.length <= 1000
  • -10^9 <= nums[i] <= 10^9

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not len(nums):
            return 0
        nums.sort()
        temp=nums[0]-1
        cnt=0
        maxi=0
        for num in nums:
            if num==temp:
                continue
            temp+=1
            if num==temp:
                cnt+=1
            else:
                if cnt>maxi:
                    maxi=cnt
                temp=num
                cnt=1
        if cnt>maxi:
            maxi=cnt
        return maxi

정렬을하고 연속된 숫자인지 세는 방식으로 구현하였는데 예외케이스를 여러번 잡아야했다.

먼저, 같은 숫자가 여러개 있을 경우를 고려 해주어야했다.

연속된 숫자가 끊어지는 순간인 else문 안에만 cnt와 max를 비교하고 기입하도록했더니 모두 연속된 숫자가 나올 경우가 고려되지 못했다.

또 nums가 비어있을 때는 nums[0]를 조회할 때 에러가 났다.

모든 에러를 잡고나니 드디어 해결되었다.

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        res = 0
        store = set(nums)
 
        for num in nums:
            streak, curr = 0, num
            while curr in store:
                streak += 1
                curr += 1
            res = max(res, streak)
        return res

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
        res = 0
        nums.sort()
 
        curr, streak = nums[0], 0
        i = 0
        while i < len(nums):
            if curr != nums[i]:
                curr = nums[i]
                streak = 0
            while i < len(nums) and nums[i] == curr:
                i += 1
            streak += 1
            curr += 1
            res = max(res, streak)
        return res

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        numSet = set(nums)
        longest = 0
 
        for num in numSet:
            if (num - 1) not in numSet:
                length = 1
                while (num + length) in numSet:
                    length += 1
                longest = max(length, longest)
        return longest

이렇게 Arrays & Hashing이 끝이 났다. 다음에는 Two Pointers 관련 문제들을 풀 예정이다.

이전 글

알고리즘 문제풀이 정리 - Arrays & Hashing (3)

Arrays & Hashing 관련 문제를 풀고 정리한 게시글입니다.