Max Increase to Keep City Skyline
개요
- 이번 포스팅은 파이썬 코딩테스트 연습문제 풀이입니다.
Leetcode에 공개된 예제이며 링크는 아래와 같습니다.
https://leetcode.com/problems/max-increase-to-keep-city-skyline/
코드
def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
n = len(grid)
answer = 0
print(grid[1][:])
for r in range(n):
for c in range(n):
new_height = min(max(grid[r][:]),max(row[c] for row in grid))
answer += (new_height - grid[r][c])
return answer
마치며
이번 포스팅은 Leetcode에 존재하는Greedy 알고리즘 중 난이도 Medium 에 해당하는 문제입니다.
조금 더 생각할 부분으로는 for 문을 3번이나 돌기 때문에 시간복잡도가 O(n^3)로 굉장히 크기 때문에 개선해보아야 할 것 같습니다.
zip(*grid) 를 사용한다면 더 효과적으로 col값을 뽑아 낼 수 있을 것 입니다.