Python에서 도시 스카이라인을 유지하기 위한 최대 증가

grid[i][j]의 각 값이 그곳에 위치한 건물의 높이를 나타내는 grid라는 2차원 배열이 있다고 가정합니다. 우리는 건물의 높이를 얼마든지 늘릴 수 있습니다. 높이 0도 건물로 간주됩니다. 결국 그리드의 네 방향 모두에서 볼 때 "스카이라인"은 원래 그리드의 스카이라인과 같아야 합니다. 도시의 스카이라인은 멀리서 볼 때 모든 건물이 형성하는 직사각형의 외부 윤곽이기 때문입니다. 따라서 건물의 높이를 높일 수 있는 최대 합계를 찾아야 합니다.

따라서 입력이 다음과 같으면

그러면 출력은 35가 됩니다. 이는 위에서 본 스카이라인이 [9, 4, 8, 7]이고 왼쪽 또는 오른쪽에서 본 스카이라인이 [8, 7, 9, 3]이기 때문입니다. 따라서 최종 행렬은 다음과 같을 수 있습니다. -

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• max_row_wise :=새 목록

• max_column_wise :=새 목록

• 카운터 :=0

• 그리드의 각 i에 대해 수행

  • max_row_wise의 끝에 i의 최대값 삽입

  • 카운터 :=카운터 + 1

• 카운터 :=0, i :=0, j :=0

• temp_list :=새 목록

• 다음을 무한히 수행하십시오 -

  • 그리드[i,j]를 temp_list에 삽입

  • 나는 :=나는 + 1

  • j가 grid[0] -1 및 i>=len(grid)의 크기와 같으면

    • max_column_wise의 끝에 temp_list의 최대값 삽입

    • 루프에서 나오다

  • 그렇지 않으면 i>=그리드 크기일 때

    • i :=0, j :=j + 1

    • max_column_wise의 끝에 temp_list의 최대값 삽입

    • 카운터 :=카운터 + 1

    • temp_list:=새 목록

• top_bottom, left_right :=max_row_wise,max_column_wise

• i, j, 값 :=0,0,0

• 다음을 무한히 수행하십시오.

  • temp :=최소 [top_bottom[i], left_right[j]]

  • j :=j + 1

  • j가 그리드의 열 길이와 같고 i가 그리드 -1의 행 수와 같으면

    • 루프에서 나오다

  • 그렇지 않으면 j가 그리드 열의 크기와 같을 때

    • 나는 :=나는+1

    • j :=0

• 반환 값

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

class Solution:
   def maxIncreaseKeepingSkyline(self, grid):
      max_row_wise = []
      max_column_wise = []
      counter = 0
      for i in grid:
         max_row_wise.append(max(i))
         counter+=1
      counter = 0
      i = 0
      j = 0
      temp_list = []
      while True:
         temp_list.append(grid[i][j])
         i+=1
         if j ==len(grid[0])-1 and i>=len(grid):
            max_column_wise.append(max(temp_list))
            break
         elif i >= len(grid):
            i = 0
            j = j + 1
            max_column_wise.append(max(temp_list))
            counter +=1
            temp_list=[]
      top_bottom, left_right = max_row_wise,max_column_wise
      i, j, value = 0,0,0
      while True:
         temp = min([top_bottom[i], left_right[j]])
         value+= abs(grid[i][j] - temp)
         j+=1
         if j == len(grid[0]) and i==len(grid)-1:
            break
         elif j == len(grid[0]):
            i = i+1
            j = 0
      return value

ob = Solution()
print(ob.maxIncreaseKeepingSkyline([[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,
3,1,0]]))

입력

[[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]

출력

35