[leetcode] 2257. Count Unguarded Cells in the Grid #3

이전에 풀었던 2257. Count Unguarded Cells in the Grid 문제를 3번째로 도전하는 중입니다.

 

이번에는 다른 분들이 푼 솔루션을 보고 개선 방법을 찾아봤습니다.

 

아뿔싸...

첫번째로 시도한 방법의 구현만 바꿨을뿐인데 100%인 답이 있더라고요...

• 참고: https://leetcode.com/problems/count-unguarded-cells-in-the-grid/solutions/6067031/beats-100-video-full-explain-3-approaches/

 

첫번째 풀이에서 walls_dict, visited를 관리하는 대신에 m x n 짜리 격자지도를 표현할 수 있는 이중 리스트를 만드는 편이 훨씬 빠르더라고요...!

• dictionary와 list의 성능 차이인 것 같은데 이것은 나중에 확인해봐야겠네요

개선된 runtime 효율!!!

 

+코드

class Solution:
    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
        grid_map = [[0]*n for _ in range(m)]
        for wall in walls:
            grid_map[wall[0]][wall[1]] = 2
        for guard in guards:
            grid_map[guard[0]][guard[1]] = 2
        
        for guard in guards:
            [row_of_guard, col_of_guard] = guard
            for row in range(row_of_guard-1, -1, -1):
                if grid_map[row][col_of_guard] == 2:
                    break
                grid_map[row][col_of_guard] = 1
            for row in range(row_of_guard+1, len(grid_map)):
                if grid_map[row][col_of_guard] == 2:
                    break
                grid_map[row][col_of_guard] = 1
            for col in range(col_of_guard-1, -1, -1):
                if grid_map[row_of_guard][col] == 2:
                    break
                grid_map[row_of_guard][col] = 1
            for col in range(col_of_guard+1, len(grid_map[0])):
                if grid_map[row_of_guard][col] == 2:
                    break
                grid_map[row_of_guard][col] = 1
        return sum(row.count(0) for row in grid_map)