Max Increase to Keep City Skyline

문제 번호, 이름: 807. Max Increase to Keep City Skyline

문제 링크: https://leetcode.com/problems/max-increase-to-keep-city-skyline

날짜: 2024/05/23

상태: 완료

 

이 문제를 고른 이유

리트코드 랜덤픽

문제 보고 처음 든 생각

문제가 길었다. 어려울거 같았다

문제를 다 읽었는데 풀이가 단번에 떠오르지 않았다

조금 더 생각을 해 보았다

 

n<=50 이니까 block 개수는 <=2500

n이 작으니까 모든 block을 iteration해도 되겠고, iteration 하면서 각 row와 column이 가진 최대 높이를 저장하면 될 것 같았다.

그리고 문제에서는 4방향에서 본다고 했지만 남북과 동서는 방향만 다를 뿐 숫자는 동일해서 사실상 2방향만 고려하면 될 것이다.

각 block이 높아질 수 있는 한도는 그 block이 속한 row와 column에 있는 다른 높은 block만큼 이므로 위에서 저장한 각 row와 column의 최대 높이를 이용해서 현재 block의 높이와의 차를 구하면 될 것이다

오.. 다행히 풀이가 바로 생각난 것 같다

풀이 v1

• 소요 시간 12분

class Solution:
    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
        answer = 0
        n = len(grid)
        max_from_row = [0 for _ in range(n)]
        max_from_column = [0 for _ in range(n)]

        for i in range(n):
            for j in range(n):
                if grid[i][j] > max_from_row[i]:
                    max_from_row[i] = grid[i][j]

                if grid[i][j] > max_from_column[j]:
                    max_from_column[j] = grid[i][j]

        for i in range(n):
            for j in range(n):
                possible_max_height = min(max_from_row[i], max_from_column[j])
                answer += (possible_max_height - grid[i][j])
        
        return answer

 

성공

다른 사람 솔루션을 봐도 이렇게 푼 것 같아서 이대로 종료 

풀이 v2

• 소요 시간

# if v2 exists

이 문제를 풀고 얻은 것

• 오늘도 하긴 했다는 성취감

메모

• 리트코드의 타이머 기능을 써 봤다