UNIST, CSE 3th

2 minute read

2279. Maximum Bags With Full Capacity of Rocks (Medium)

가방에 돌을 채우는 문제, 최대한 채울수 있는 가방의 개수를 반환하는 문제. 용량이 거의 가득찬 가방을 기준으로 정렬하여 계산.

class Solution:
    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:
        n = len(rocks)
        res = 0
        arr = [capacity[i] - rocks[i] for i in range(n)]
        arr.sort()
        for i in range(n):
            if arr[i] <= additionalRocks:
                additionalRocks -= arr[i]
                res += 1
            else:
                break
        return res

130. Surrounded Regions (Medium)

오랜만에 건드려보는 board 관련 문제.. 근데 잘 안풀린다. 아이디어는 현재 탐색중인 영역을 C로 표기하고 이게 삭제되지 않을 증거가 발견되었을 때 return 하지 않고 계속 탐색하여 모든 영역을 밝힌다. 그리고 return을 해서 P인지 F인지 설정을 하게 한다. 이렇게 하는 이유는 board에서 for문을 돌리면서 같은 point에서 동일한 convert 함수를 실행하지 않기 위함이다. 그러나.. time exceeded가 마지막 테스트 케이스에서 떠버리고 말았다.

이유는 간단하다. 탐색방식이 너무나 정직해서 그렇다. 차례대로 돌면서 영역을 탐색하고 그 탐색한 영역을 피하기 위해서 여러가지 조건이 사용되고 복잡해졌다. 체킹을 하고 나중에 바꾸면 된다는 아이디어는 여전히 동일하나, 탐색방법이 너무나 정직해서 코드가 너무 복잡해졌다. 머리를 비우고 다시 코드를 짜보았다.

class Solution:

    def convert(self, board, x, y, m, n):
        res = False
        # bound check
        if x < 0 or x >= m or y < 0 or y >= n:
            return False
        # already checked or current checking
        if board[x][y] == 'X' or board[x][y] == 'C':
            return False
        if board[x][y] == 'P':
            return True
            # board[x][y] == 'F'
        if board[x][y] == 'O':
            if x == m - 1 or x == 0 or y == n - 1 or y == 0:
                board[x][y] = 'P'
                res = True

        # C : current checking
        # P : pass -> O
        # F : fail -> X
        if res == False:
            board[x][y] = 'C'

        dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        for p in dirs:
            res |= self.convert(board, x + p[0], y + p[1], m, n)
        if res:
            board[x][y] = 'P'
        else:
            board[x][y] = 'F'
        return res

    def solve(self, board: List[List[str]]) -> None:
        m, n = len(board), len(board[0])
        for x in range(m):
            for y in range(n):
                self.convert(board, x, y, m, n)
        
        for x in range(m):
            for y in range(n):
                if board[x][y] == 'P':
                    board[x][y] = 'O'
                if board[x][y] == 'F':
                    board[x][y] = 'X'
        
                    

class Solution:

    def convert(self, board, x, y, m, n):
        # bound check
        if x < 0 or x >= m or y < 0 or y >= n:
            return
        if board[x][y] == 'X' or board[x][y] == 'P':
            return
        if board[x][y] == 'O':
            board[x][y] = 'P'
        dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        for p in dirs:
            self.convert(board, x + p[0], y + p[1], m, n)

    def solve(self, board: List[List[str]]) -> None:
        m, n = len(board), len(board[0])
        for x in range(m):
            self.convert(board, x, 0, m, n)
            self.convert(board, x, n - 1, m, n)

        for y in range(n):
            self.convert(board, 0, y, m, n)
            self.convert(board, m - 1, y, m, n)
        
        for x in range(m):
            for y in range(n):
                if board[x][y] == 'O':
                    board[x][y] = 'X'
                if board[x][y] == 'P':
                    board[x][y] = 'O'

border line 부터 탐색하는 코드이다. 훨씬 간단해지고 보기 좋아졌다. 가장자리에 있는 O를 기준으로 영역을 확장해나가면서 P로 만들고 P로 바뀌지 않은 O들은 X로 바꾸면 문제를 풀 수 있다.

You may also enjoy