TIL 21/05/14

1

리트코드 Time Limit Exceeded 문제를 풀었다.

처음에 그냥 완전탐색으로 풀었다.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        answer = []
        length = len(nums)
        for i in range(length): # i is window length
            maxVal = (-1)*(10**5)*length
            start = 0
            end = start + i
            while end <= length-1:
                temp = sum(nums[start:end+1])
                if temp >= maxVal:
                    maxVal = temp
                start += 1
                end += 1
            answer.append(maxVal)
        return max(answer)

바로 시간초과뜸; 왜 dp문제겠냐.. 멍청했다. 아니면 적어도 내 코드풀이에 대한 시간복잡도라도 생각했어야했는데

너무 안일했다. 그래서 바로 dp 배열을 이용한 풀이를 떠올렸다

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        length = len(nums)
        dp = [i for i in nums] # dp[i] : i가 endIndex로 끝나는 리스트에서 가지는 정답
        for i in range(1, length):
            dp[i] = max(dp[i-1]+nums[i], nums[i])
        return max(dp)

해결

 

2

리트코드 Surrouned Regions 문제를 풀었다.

외곽에있는 놈들과 그룹이 묶이면 X로 플립하면 안되는 부분에 대한 예외처리를 위해 너무 스파게티 코드를 만들어버렸다;;

다음과 같이 일단 풀긴풀었다

from collections import deque
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        
        board_length = len(board)
        
        board_row_length = len(board)
        board_col_length = len(board[0])
        vis = [[0 for i in range(board_col_length)] for i in range(board_row_length)]
        # print(vis)
        position = []
        q = deque()
        for i in range(1, board_row_length-1):
            for j in range(1, board_col_length-1):
                # print("i is : " + str(i) + " and j is : "+ str(j))
                # print(i,j)
                if board[i][j] == "O": # 탐색시작
                    # print("i is : " + str(i) + " and j is : "+ str(j))
                    q.append([i, j])
                    position.append([i, j])
                    vis[i][j] = 1
                    flag = False
                    while q:
                        curX, curY = q.popleft()
                        for dir in range(4):
                            nx = curX + dx[dir]
                            ny = curY + dy[dir]
                            if (nx == 0 and board[nx][ny] == 'O') or (nx == board_row_length-1 and board[nx][ny]=='O') or (ny == 0 and board[nx][ny]=='O')or (ny == board_col_length-1 and board[nx][ny]=='O'):
                                position = []
                                q.clear()
                                vis = [[0 for r in range(board_col_length)] for c in range(board_row_length)]

                                flag = True
                                break
                            if nx == 0 or nx == board_row_length or ny == 0 or ny == board_col_length:
                                continue
                            
                            
                            if vis[nx][ny] != 0 or board[nx][ny] == 'X':
                                continue
                            if board[nx][ny] == 'O':
                                vis[nx][ny] = 1
                                q.append([nx, ny])
                                position.append([nx, ny])
                                
                        if flag == True:
                            flag = False
                            break
                   
                    # 모두 탐색 후 해당 탐색 좌표 X로 변경
                    # print(position)
                    for k in range(len(position)):
                        board[position[k][0]][position[k][1]] = "X"
                    position = []
                    
        return board

외곽에 대한 처리를 미리해둔다면 훨씬 더 잘짤 수 있지않을까..? 나는 처음에 잘못생각해서 뒤로돌릴 수가없었다.. 

이럴때는 그냥 아예 처음부터 다시 짜는게 맞는건가? 

아직 쌩초보라 잘모르겠다..